150.逆波兰表达式求值

链接：150.逆波兰表达式求值
难度：Medium
标签：栈、数组、数学
简介：根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

题解 1 - java

• 编辑时间：2020-02-13
• 执行用时：20ms
• 内存消耗：46.8MB
• 编程语言：java
• 解法介绍：使用栈，数字压栈，符号出栈。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<String>();
		int a, b;
		for (String s : tokens) {
			switch (s) {
			case "+":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((a + b) + "");
				break;
			case "-":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((b - a) + "");
				break;
			case "*":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((a * b) + "");
				break;
			case "/":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((b / a) + "");
				break;
			default:
				stack.push(s);
				break;
			}
		}
		return Integer.parseInt(stack.pop());
    }
}

题解 2 - typescript

• 编辑时间：2021-03-20
• 执行用时：724ms
• 内存消耗：48.2MB
• 编程语言：typescript
• 解法介绍：栈。

function evalRPN(tokens: string[]): number {
  const opMap: Record<string, (num1: number, num2: number) => number> = {
    '+': (num1, num2) => num1 + num2,
    '-': (num1, num2) => num1 - num2,
    '*': (num1, num2) => num1 * num2,
    '/': (num1, num2) => ~~(num1 / num2),
  };
  const stack: number[] = [];
  for (const token of tokens) {
    console.log(token, stack);
    if (token === '+' || token === '-' || token === '*' || token === '/') {
      const num2 = stack.pop()!;
      const num1 = stack.pop()!;
      stack.push(opMap[token](num1, num2));
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

题解 3 - cpp

• 编辑时间：2021-12-23
• 执行用时：12ms
• 内存消耗：11.6MB
• 编程语言：cpp
• 解法介绍：栈存储。

class Solution {
   public:
    int s2i(string str) {
        int ans = 0, f = 1;
        for (int i = 0; i < str.size(); i++) {
            if (i == 0 && str[i] == '-') {
                f = -1;
                continue;
            }
            ans = ans * 10 + str[i] - '0';
        }
        return ans * f;
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();
                int ans;
                if (str == "+")
                    ans = num2 + num1;
                else if (str == "-")
                    ans = num2 - num1;
                else if (str == "*")
                    ans = num2 * num1;
                else
                    ans = num2 / num1;
                s.push(ans);
            } else {
                s.push(s2i(str));
            }
        }
        return s.top();
    }
};