什么是波兰表达式

a + b * (c - d) + e/f


逆波兰表达式

例子

9+(3-1)*3+10/2 的逆波兰表达式为：9 3 1 - 3 * + 10 2 / +

如何得到

输出9 -> 输出值：9
+ 入栈 -> 栈内：+
( 入栈 -> 栈内：+ (

-入栈 -> 栈内：+ ( -

/入栈 -> 栈内：+ /



C 实现

#include <stdio.h>
#include <string.h>

struct Node
{
char data[1000];
int top = -1;
}stack;

int isPriority(char a, char top);

int main(int argc, char const *argv[])
{
char str[1000];
gets(str);
int len = strlen(str);
for(int i=0; i<strlen(str); i++){
if(str[i]>=48 && str[i]<=57){//输出数字
if(i<strlen(str)-1 && (str[i+1]>=48 && str[i+1]<=57)){
printf("%c", str[i]);
}else{
printf("%c ", str[i]);
}
}else{//入栈或者出栈
if(stack.top==-1 || isPriority(str[i], stack.data[stack.top])){//当前运算符优先级不低于栈顶优先级
//入栈
stack.data[++stack.top] = str[i];
}else{
if(str[i] == ')'){//出栈至'('
while (stack.data[stack.top] != '('){
printf("%c ", stack.data[stack.top]);
stack.top--;
}
stack.top--;//将'('出栈但是不输出
}else{//全部出栈
while (stack.top != -1){
printf("%c ", stack.data[stack.top]);
stack.top--;
}
//当前符号入栈
stack.data[++stack.top] = str[i];
}
}

}
}
//全部出栈
while (stack.top != -1){
printf("%c ", stack.data[stack.top]);
stack.top--;
}
return 0;
}

int isPriority(char a, char top){
//判断a运算符和栈顶top运算符的优先级，如果a不低于栈顶top，输出1，否则输出0
if(((a=='+')||(a=='-')) && ((top=='*')||(top=='/')) || a == ')'){//低于栈顶优先级
return 0;
}
return 1;
}


逆波兰表达式的计算

1. 将队列中的数据依次出队，然后压栈；

2. 在出队的过程中如果遇到运算符，则从栈中弹出2个运算数，分别作为右运算数和左运算数，进行运算；

3. 将步骤2的运算结果入栈；

4. 跳入步骤1，继续进行出队操作。

leetcode 150 Evaluate Reverse Polish Notation

题目

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input represents a valid arithmetic expression in a reverse polish notation. The answer and all the intermediate calculations can be represented in a 32-bit integer.

Ex

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9


Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6


Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22


Constraints:

1 <= tokens.length <= 10^4

tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].

V1-基本思路

实现

import java.util.Stack;

public class T150_EvaluateReversePolishNotation {

/**
* 1. 遍历 tokens，压入 stack 内
*
* @param tokens 字符串数组
* @return 结果
*/
public int evalRPN(String[] tokens) {
String operators = "+-*/";
Stack<String> stack = new Stack<>();

int result = 0;

// 是否为操作符
for(String token : tokens) {
// 操作符
if(operators.contains(token)) {
String top1 = stack.pop();
String top2 = stack.pop();

// 计算的时候，top2 要在前面
result = calc(top2, token, top1);

// 把结果压入栈
} else {
// 数字压入栈内
}
}

// 最后的出栈
result = Integer.parseInt(stack.pop());

return result;
}

private int calc(String top2, String operator, String top1) {
switch (operator) {
case "+":
return Integer.parseInt(top2) + Integer.parseInt(top1);
case "-":
return Integer.parseInt(top2) - Integer.parseInt(top1);
case "*":
return Integer.parseInt(top2) * Integer.parseInt(top1);
case "/":
return Integer.parseInt(top2) / Integer.parseInt(top1);
default:
throw new UnsupportedOperationException();
}
}

}


V2-更强的算法

class Solution {
int idx;

public int evalRPN(String[] tokens) {
idx = tokens.length - 1;
return eval(tokens);
}

private int eval(String[] tokens) {
if(!isOperator(tokens[idx]))
return Integer.valueOf(tokens[idx--]);
char operator = tokens[idx--].charAt(0);
int right = eval(tokens);
int left = eval(tokens);
if(operator == '+') return left + right;
if(operator == '-') return left - right;
if(operator == '*') return left * right;
if(operator == '/') return left / right;
return -1;
}

private boolean isOperator(String token) {
if(token.length() > 1) return false;
char c = token.charAt(0);
return c == '+' || c == '-' || c == '*' || c == '/';
}
}


参考资料

https://zhuanlan.zhihu.com/p/65110137

https://zhuanlan.zhihu.com/p/94431722

https://leetcode.com/problems/evaluate-reverse-polish-notation/