首页 > 代码库 > Evaluate Reverse Polish Notation

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.

Some examples:

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

解题方案:

该题借助一个栈,遍历tokens时,如果当前不为"+","-","*","/",则入栈,否则将栈顶的两个元素出栈后,运算后结果入栈。下面是该题代码:

 1 class Solution { 2 public: 3     int evalRPN(vector<string> &tokens) { 4         stack<int> result; 5         int a, b; 6         for (vector<string>::iterator ix = tokens.begin(); ix != tokens.end(); ++ix) { 7             if (*ix == "+" || *ix == "-" || *ix == "*" || *ix == "/") { 8                 a = result.top(); 9                 result.pop();10                 b = result.top();11                 result.pop();12                 if (*ix == "+") {13                     result.push(b + a);14                 }15                 if (*ix == "-") {16                     result.push(b - a);17                 }18                 if (*ix == "*") {19                     result.push(b * a);20                 }21                 if (*ix == "/") {22                     result.push(b / a);23                 }24             } else {25                 result.push(atoi((*ix).c_str()));26             }27         }28         return result.top();29     }30 };

 

Evaluate Reverse Polish Notation