Leetcode: Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

My Submissions

Total Accepted: 57639 Total Submissions: 254722 Difficulty: Medium

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

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

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Subscribe to see which companies asked this question

Hide Tags

 Stack

Show Similar Problems

----------------------------------------------------------------------------------

思路：

典型的stack问题。逐一扫描每个token，如果是数字，则push入stack，如果是运算符，则从stack中pop出两个数字，进行运算，将结果push回stack。最后留在stack里的数即为最终结果。

以题中例子说明

exp:     2    1      +    3      *

stack:   2    2,1   3    3,3   9

///////////////////////////////////////////////////////////////////////

class Solution {

 public:

        int evalRPN(vector<string>& tokens) {

               stack<int> tokTmp;

               for (int i = 0; i<tokens.size(); i++){

                      //tokens[i] is a string, so "" is used!

                      if ((tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")){

                            int y = tokTmp.top();

                            tokTmp.pop();

                            int x = tokTmp.top();

                            tokTmp.pop();

                            if (tokens[i] == "+")tokTmp.push(x + y);

                            else if (tokens[i] == "-")tokTmp.push(x - y);

                            else if (tokens[i] == "*")tokTmp.push(x*y);

                            else if (tokens[i] == "/")tokTmp.push(x / y);

                      }

                      else {

                            int x = stoi(tokens[i], nullptr, 10);

                            tokTmp.push(x);

                      }

               }

               return tokTmp.top();

        }

 };