[关闭]
@hainingwyx 2017-07-23T14:40:30.000000Z 字数 953 阅读 621

逆波兰表示

数据结构


20世纪50年代,波兰逻辑学家提出了一种不需要括号的后缀表示法,也成为逆波兰(Reverse Polish Notatiojn ,RPN)表示。

后缀表达式:所有的符号都要在要运算的数字的后面出现。例如:“9+(3-1)x3+10/2”后缀表达式为:“9 3 1 - 3 * + 10 2 / +”

后缀表达式计算结果

对于“9 3 1 - 3 * + 10 2 / +”为例:

  1. 初始化空栈
  2. 9、3、1进栈,栈为9-3-1
  3. 对于“-”,1出栈作为减数,3出栈作为被减数,结果得到2再次进栈,栈为9-2
  4. 3 进栈,栈2为9-3-2
  5. 对于“*”,3出栈,2出栈,得到6,结果入栈,栈为9-6
  6. 对于“+”,6出栈,9出栈,得到15,结果入栈,栈为15
  7. 10和2进栈,栈为15-10-2
  8. 对于“\”,2出栈,10出栈,得到5,结果入栈,栈为15-5
  9. 对于“+”,5出栈,15出栈,得到20,结果入栈,栈为20
  10. 20出栈,栈为空。
  1. import java.util.Stack;
  2. public class RPN {
  3. public static int evalRPN(String[] tokens) {
  4. Stack<Integer> stack = new Stack<Integer>();
  5. for(int i = 0;i<tokens.length;i++){
  6. try{
  7. int num = Integer.parseInt(tokens[i]);
  8. stack.add(num);
  9. }catch (Exception e) {
  10. int b = stack.pop();
  11. int a = stack.pop();
  12. stack.add(get(a, b, tokens[i]));
  13. }
  14. }
  15. return stack.pop();
  16. }
  17. private static int get(int a,int b,String operator){
  18. switch (operator) {
  19. case "+":
  20. return a+b;
  21. case "-":
  22. return a-b;
  23. case "*":
  24. return a*b;
  25. case "/":
  26. return a/b;
  27. default:
  28. return 0;
  29. }
  30. }
  31. public static void main(String[] args) {
  32. String[] strlist = {"2", "1", "+", "3", "*"};
  33. System.out.println(evalRPN(strlist));
  34. }
  35. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注