返回

[Leetcode]150. Evaluate Reverse Polish Notation(C++)

题目描述

题目链接:150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

例子

例子 1

Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

例子 2

Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

例子 3

Input:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

Follow Up

Note

  • Division between two integers should truncate toward zero.
  • It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Constraints

  • 1 <= tokens.length <= 10^4
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

解题思路

从例子中可以看出,求解思路是:遍历 vector,遇到数字不用管,遇到符号,则取前两个数字进行相应操作,然后将得出来的结果放入数组中继续遍历。符合这种操作的数据结构是栈。需要注意一点是做除法运算时,弹出的第一个数实际上是除数,然后才是被除数。代码如下:

#include <stack>
#include <string>
#include <vector>

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> nums;
        int result = 0;
        for (auto c : tokens) {
            if (c == "+" || c == "-" || c == "/" || c == "*") {
                performOperate(nums, c[0]);
            } else {
                nums.push(std::stoi(c));
            }
        }
        return nums.top();
    }

private:
    void performOperate(std::stack<int>& nums, char op) {
        int val1 = nums.top();
        nums.pop();
        int val2 = nums.top();
        nums.pop();
        int res = val2;
        switch (op) {
            case '+':
                res += val1;
                break;
            case '-':
                res -= val1;
                break;
            case '*':
                res *= val1;
                break;
            case '/':
                res /= val1;
                break;
            default:
                break;
        }
        nums.push(res);
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 150.EvaluateReversePolishNotation.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy