Leetcode150. 逆波兰表达式求值

题目

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释: 
  ((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

C++解法

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
class Stack {
private:
    vector<int> elems;
public:
    void push(int const& elem) {
        elems.push_back(elem);
    }
    int pop() {
        if (elems.empty()) throw out_of_range("Stack<>::pop(): empty stack");
        int back = elems.back();
        elems.pop_back();
        return back;
    }
    int top() const {
        if (elems.empty()) throw out_of_range("Stack<>::top(): empty stack");
        return elems.back();
    }
    bool empty() const {
        return elems.empty();
    }
    long size() const {
        return elems.size();
    }
    void printElements() {
        for (auto i : elems) {
            cout << i << " ";
        }
        cout << endl;
    }
};

class Solution {
public:
    bool isNumber(char c) { return c >= 48 && c <= 57; }
    int getNumber(string numberString) {
        int result = 0;
        int sign = 1;
        for (auto c: numberString) {
            if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else result = result * 10 + (c - '0');
        }
        return sign * result;
    }
    int evalRPN(vector<string>& tokens) {
        Stack numbers;
        for (auto token: tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int rhs = numbers.pop();
                int lhs = numbers.pop();
                int result = 0;
                if (token == "+") result = lhs + rhs;
                else if (token == "-") result = lhs - rhs;
                else if (token == "*") result = lhs * rhs;
                else if (token == "/") result = lhs / rhs;
                numbers.push(result);
            } else {
                numbers.push(getNumber(token));
            }
        }
        return numbers.pop();
    }
};

int main(int argc, const char * argv[]) {
    // insert code here...
    Solution solution;
    vector<string> vec;
    vec = {"2", "1", "+", "3", "*"};
    cout << solution.evalRPN(vec) << endl;
    vec = {"4", "13", "5", "/", "+"};
    cout << solution.evalRPN(vec) << endl;
    vec = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    cout << solution.evalRPN(vec) << endl;
    vec = {"10","38","39","11","-","-","-","2","-","37","-7","-","+","1","+","-8","34","-","-15","+","-","35","-","2","/","8","-","0","-4","+","-","1","-","-2","22","+","-","16","-","4","+","17","31","+","9","-","-","3","-2","-","-","35","27","-","+","31","-","-13","+","6","+","-18","+","-17","-2","-","-","0","-","-13","-","39","22","-","4","7","-","+","2","18","-","-","+","-6","+","-11","+","27","18","-","+","29","28","-2","-5","-15","26","+","-","-","-","11","+","-","-1","+","7","28","-","-","-","38","+","28","-","14","+","12","24","-","2","38","-","-","+","12","-","30","-","32","1","-","-","10","-12","+","+","-6","-","38","34","+","+","35","+","10","-","37","+","11","-","36","+","39","-","36","30","-","+","20","+","8","-","18","31","+","-4","+","+","23","-4","-10","-2","8","-12","+","+","10","-","15","9","2","+","25","-","-","-15","21","-2","-10","*","+","+","25","29","35","+","-","3","+","+","17","+","-","-","10","-4","+","21","23","-5","+","+","+","+","-","+","-","-1","+","7","-","-","22","-","-15","+","7","7","+","17","-","-","-16","21","-","35","36","9","+","9","2","30","-12","-","+","-","-","+","-","-20","+","+","27","-","12","-","7","20","+","+","36","+","34","7","+","+","-2","+","22","-","20","+","27","-","37","-8","30","1","18","-10","-","-","-","+","-20","+","-","36","-8","39","+","-","-","+","25","+","33","+","3","-","14","+","34","20","12","-4","+","-15","+","-","-10","-8","-13","-","6","24","35","-","-","-","27","-","-","-16","+","+","-3","-17","25","21","18","+","19","+","-","18","-","-9","+","+","-","-","-","-","35","29","+","25","*","12","-","4","+","-6","-7","8","+","+","-10","8","-","-","-","-","6","+","-18","-","29","+","10","+","9","+","23","31","-","-","18","+","36","/","-5","-","4","-","5","-8","-","-14","-6","31","-","+","+","22","+","-","22","-18","27","+","1","17","+","-","-20","28","+","+","-18","6","2","4","*","+","-","+","+","-","36","-","22","-","-8","7","34","+","+","26","+","+","30","10","-1","+","+","-","11","+","9","-20","-9","+","11","-","-5","-6","+","-","17","+","30","+","-","-9","10","+","+","+","12","26","-","-","6","-","33","14","+","17","18","+","29","-","34","-","*","-19","+","2","+","-","16","+","-19","-","17","0","6","-","+","-19","-18","-","-","18","27","-17","-2","27","-","-17","+","+","+","+","36","+","-17","17","*","*","+","*"};
    cout << solution.evalRPN(vec) << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation