150-逆波兰表达式

LeetCode 150. Evaluate Reverse Polish Notation

LeetCode-150

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

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

Note that 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.

Example 1:

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

method: 栈

stoi() // 将 string 转换为 int

如果是运算符，就将栈顶的两个元素弹出进行运算，再将结果入栈
注意：减法和除法，第一个弹出的是减数（除数），第二个弹出的是被减数（被除数）

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (auto s : tokens) {
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            int num1 = st.top();
            st.pop();
            int num2 = st.top();
            st.pop();
            if (s == "+") st.push(num2 + num1);
            if (s == "-") st.push(num2 - num1);
            if (s == "*") st.push(num2 * num1);
            if (s == "/") st.push(num2 / num1);
        }
        else st.push(stoi(s));  // stoi()将string转为int
    }
    return st.top();
}