LeetCode-150-Evaluate Reverse Polish Notation

概述算法描述： Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two intege

算法描述：

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

ValID operators are +, -, *, /. Each operand may be an integer or another Expression.

Note:

division between two integers should truncate toward zero. The given rpn Expression is always valID. That means the Expression would always evaluate to a result and there won‘t be any divIDe by zero operation.

Example 1:

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

Example 2:

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

Example 3:

input: ["10","6","9","-11","*","17","+"]Output: 22Explanation:   ((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

解题思路：逆波特兰表达式，用栈辅助模拟。

    int evalrpn(vector<string>& tokens) {        if(tokens.size()==0) return 0;        stack<int> stk;        for(auto c : tokens){            if(c == "+" || c == "-" || c== "*" || c=="/"){                int right = stk.top();                stk.pop();                int left = stk.top();                stk.pop();                int ans;                if(c == "+") ans = left + right;                if(c == "-") ans = left - right;                if(c == "*") ans = left * right;                if(c == "/") ans = left / right;                stk.push(ans);            }else{                stk.push(stoi(c));            }        }        return stk.top();    }

总结

以上是内存溢出为你收集整理的LeetCode-150-Evaluate Reverse Polish Notation全部内容，希望文章能够帮你解决LeetCode-150-Evaluate Reverse Polish Notation所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。