逆波兰表达式求值

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，150. Evaluate Reverse Polish Notation

先看题目描述

6f7q1O.png

大意就是给定一个逆波兰表达式，让我们求出表达式的结果并返回

算法和思路

逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也被称为后缀表达式。逆波兰表达式实际上就是对树的后根遍历

栈

对逆波兰表达式求结果可以用栈解决，构建一个栈里面存储操作数，然后遍历字符串数组

  • 当遇到运算符时，则连续将两个操作数出栈，先出栈的为右操作数，后出栈的为左操作数，然后对左操作数和右操作数进行相应运算，并将结果压入栈顶
  • 当遇到操作数时，则将操作数压入栈顶

由于题目保证给定的逆波兰表达式总是有效的，最终遍历完字符串数组后，栈中会只剩下一个操作数，就是我们要返回的计算结果

算法和思路

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String s: tokens) {
            if (s.equals("+")) {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num1 + num2);
            } else if (s.equals("-")) {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 - num1);
            } else if (s.equals("*")) {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num1 * num2);
            } else if (s.equals("/")) {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 / num1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}

数组模拟栈

下面的代码同样是使用的栈，但是却是用整型数组来模拟栈，有一个指针 top 指向栈顶，来进行存取元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int evalRPN(String[] tokens) {
        int[] arr = new int[tokens.length];
        int top = -1;
        for (String s: tokens) {
            if (s.equals("+")) {
                top--;
                arr[top] += arr[top + 1];
            } else if (s.equals("-")) {
                top--;
                arr[top] -= arr[top + 1];
            } else if (s.equals("*")) {
                top--;
                arr[top] *= arr[top + 1];
            } else if (s.equals("/")) {
                top--;
                arr[top] /= arr[top + 1];
            } else {
                top++;
                arr[top] = Integer.valueOf(s);
            }
        }
        return arr[top];
    }
}