首页 > 代码库 > LeetCode OJ——练习笔记（1）Evaluate Reverse Polish Notation

LeetCode OJ——练习笔记（1）Evaluate Reverse Polish Notation

2024-07-10 15:25:37   218人阅读

院招终于开始了，然后期待与兴奋过后却是面临着笔试一次又一次的失败，然后开始留意到LeetCode。

也想自己去体验一下诸多大牛通向无限coding路上都攻克过的一关。

话不多说，贴出原题：

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

该题知识点用到了数据结构中学过的逆波兰表达式，思路就是：借助栈，遇数字则入栈，遇操作数则取栈顶两个字符出栈，返回运算结果再入栈，到最后栈里剩下的唯一数字就是结果，
稍微注意一下可能出现的只有一个数字的这种情况，还有就是先出栈的作为操作数2，后出栈的作为操作符1，这在减法和除法中可能会出错。
 1 class Solution { 2 public: 3     int evalRPN(vector<string> &tokens) { 4          stack<int> stk; 5         for(int i=0;i<tokens.size();i++){ 6             if(tokens[i].length()==1 && (tokens[i][0]>‘9‘ || tokens[i][0]<‘0‘)) 7             { 8                 int o2 = stk.top(); 9                 stk.pop();10                 int o1 = stk.top();11                 stk.pop();12                 switch(tokens[i][0])13                 {14                     case ‘+‘: stk.push(o1+o2); break;15                     case ‘-‘: stk.push(o1-o2); break;16                     case ‘*‘: stk.push(o1*o2); break;17                     case ‘/‘: stk.push(o1/o2); break;18                 }19             }20             else21                 stk.push(atoi(tokens[i].c_str()));22         }23         return stk.top();24     }25 };

 


联系
我们