问题分析

对所给字符串进行遍历，遇到数字字符就压入栈stack内，遇到+-*/符号就pop处栈的两个元素，进行该字符运算处理

代码实现

  1. package com.wztlink1013.problems.leetcode.editor.cn;
  3. // P150.逆波兰表达式求值
  4. // P150.evaluate-reverse-polish-notation
  5. //根据 逆波兰表示法，求表达式的值。 
  6. //
  7. // 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 
  8. //
  9. // 
  10. //
  11. // 说明： 
  12. //
  13. // 
  14. // 整数除法只保留整数部分。 
  15. // 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 
  16. // 
  17. //
  18. // 
  19. //
  20. // 示例 1： 
  21. //
  22. // 输入: ["2", "1", "+", "3", "*"]
  23. //输出: 9
  24. //解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
  25. // 
  26. //
  27. // 示例 2： 
  28. //
  29. // 输入: ["4", "13", "5", "/", "+"]
  30. //输出: 6
  31. //解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
  32. // 
  33. //
  34. // 示例 3： 
  35. //
  36. // 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  37. //输出: 22
  38. //解释: 
  39. //该算式转化为常见的中缀算术表达式为：
  40. //  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
  41. //= ((10 * (6 / (12 * -11))) + 17) + 5
  42. //= ((10 * (6 / -132)) + 17) + 5
  43. //= ((10 * 0) + 17) + 5
  44. //= (0 + 17) + 5
  45. //= 17 + 5
  46. //= 22 
  47. //
  48. // 
  49. //
  50. // 逆波兰表达式： 
  51. //
  52. // 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 
  53. //
  54. // 
  55. // 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 
  56. // 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 
  57. // 
  58. //
  59. // 逆波兰表达式主要有以下两个优点： 
  60. //
  61. // 
  62. // 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 
  63. // 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。 
  64. // 
  65. // Related Topics 栈 
  66. // 👍 213 👎 0
  69. import java.util.Stack;
  71. public class P150EvaluateReversePolishNotation{
  72.     public static void main(String[] args) {
  73.         Solution solution = new P150EvaluateReversePolishNotation().new Solution();
  74.         String[] tokens_1 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
  75.         int temp = solution.evalRPN(tokens_1);
  76.         System.out.println(temp);
  78.     }
  80. //leetcode submit region begin(Prohibit modification and deletion)
  81. class Solution {
  82.     public int evalRPN(String[] tokens) {
  83.         Stack<String> stack = new Stack<>();
  85.         String temp = "0";
  86.         stack.push(temp);
  88.         for (String token : tokens) {
  89.             int sum = 0;
  90.             if (token.equals("+")) {
  91.                 sum += Integer.parseInt(stack.pop()) + Integer.parseInt(stack.pop());
  92.                 String str = String.valueOf(sum);
  93.                 stack.push(str);
  94.             } else if (token.equals("-")) {
  95.                 int i = Integer.parseInt(stack.pop());
  96.                 int j = Integer.parseInt(stack.pop());
  97.                 sum += j-i;
  98.                 String str = String.valueOf(sum);
  99.                 stack.push(str);
  100.             } else if (token.equals("*")) {
  101.                 sum += Integer.parseInt(stack.pop()) * Integer.parseInt(stack.pop());
  102.                 String str = String.valueOf(sum);
  103.                 stack.push(str);
  104.             } else if (token.equals("/")) {
  105.                 int i = Integer.parseInt(stack.pop());
  106.                 int j = Integer.parseInt(stack.pop());
  107.                 sum += j / i;
  108.                 String str = String.valueOf(sum);
  109.                 stack.push(str);
  110.             } else {
  111.                 stack.push(token);
  112.             }
  113.         }
  114.         int result = Integer.parseInt(stack.pop());
  115.         return result;
  116.     }
  117. }
  118. //leetcode submit region end(Prohibit modification and deletion)
  120. }