题目:
Evaluate the value of an arithmetic expression in Reverse Polish Notation
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
用逆波兰式(后缀表达式)计算算术表达式的值。有效运算符是+,-,*,/。每个操作数可以是一个整数,也可以是另一个表达式。
逆波兰式:
实现逆波兰式的算法,难度并不大,但为什么要将看似简单的中序表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。
思路:
- 将给定的字符串数组挨个判断是否为Integer压入栈,遇到运算符时栈弹出两个数字计算,再将计算结果入栈
- 若是给的后缀表达式数组合理最后弹出的数字即为结果
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(calculate(tokens[i], num1, num2));
} else {
int number = Integer.parseInt(tokens[i]);
stack.push(number);
}
}
return stack.pop();
}
private int calculate(String operator, int a, int b) {
switch (operator) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
case "/":
return a / b;
default:
return 0;
}
}
}
附:
评论区看到个让人眼前一亮的方法,利用异常来做的
不过也有持不赞同的意见
老实说,异常不建议用作逻辑判断,它应该只用于检验错误,使用异常会使得运行效率变低,内部语句不会进行任何优化,《effective java》有一条就是这么写的
import java.util.Stack;
public class Solution {
public 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 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;
}
}
}