20世纪50年代，波兰逻辑学家提出了一种不需要括号的后缀表示法，也成为逆波兰(Reverse Polish Notatiojn ,RPN)表示。
后缀表达式：所有的符号都要在要运算的数字的后面出现。例如：“9+(3-1)x3+10/2”后缀表达式为：“9 3 1 - 3 * + 10 2 / +”
后缀表达式计算结果
对于“9 3 1 - 3 * + 10 2 / +”为例：
- 初始化空栈
- 9、3、1进栈，栈为9-3-1
- 对于“-”，1出栈作为减数，3出栈作为被减数，结果得到2再次进栈，栈为9-2
- 3 进栈，栈2为9-3-2
- 对于“*”，3出栈，2出栈，得到6，结果入栈，栈为9-6
- 对于“+”，6出栈，9出栈，得到15，结果入栈，栈为15
- 10和2进栈，栈为15-10-2
- 对于“\”，2出栈，10出栈，得到5，结果入栈，栈为15-5
- 对于“+”，5出栈，15出栈，得到20，结果入栈，栈为20
- 20出栈，栈为空。
import java.util.Stack;
public class RPN {
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
try{
int num = Integer.parseInt(tokens[i]);
stack.add(num);
}catch (Exception e) {
int b = stack.pop();
int a = stack.pop();
stack.add(get(a, b, tokens[i]));
}
}
return stack.pop();
}
private static int get(int a,int b,String operator){
switch (operator) {
case "+":
return a+b;
case "-":
return a-b;
case "*":
return a*b;
case "/":
return a/b;
default:
return 0;
}
}
public static void main(String[] args) {
String[] strlist = {"2", "1", "+", "3", "*"};
System.out.println(evalRPN(strlist));
}
}
