【leetcode C++】逆波兰表达式求值-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode C++】逆波兰表达式求值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

逆波兰表达式求值

题目

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。

每个操作数（运算对象）都可以是一个整数或者另一个表达式。

两个整数之间的除法总是 向零截断 。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位 整数表示。

题目链接

. - 力扣（LeetCode）

文字和画图分析

这里我们主要是理解后缀如何转化成中缀

如：后缀 2 1 + 3 *

中缀（2 + 1） * 3

实际上是先算 2 + 1 得到 3 ，再算 3 * 3

这里我们利用栈前进后出的思想

遇到数字就 push，遇到运算符就记录栈顶的两个元素，再进行运算

注意：文章来源地址https://www.toymoban.com/news/detail-840488.html

由于很可能出现负数的情况，不能只通过比较字符串的第一个首字符来判断是否是运算符还是数字，这里就直接比较两个字符串

让字符串站化成整数，我们这里使用函数stoi

代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
          stack<int> t;
          for(int i = 0;i < tokens.size();i++)
          {
              char tmp = tokens[i][0];
              if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
              {
                   int right = t.top();
                 t.pop();
                 int left = t.top();
                 t.pop();
                 switch(tmp)
                 {
                    case '+':
                     t.push(left + right);
                     break;
                     case '-':
                     t.push(left - right);
                      break;
                      case '*':
                       t.push(left * right);
                       break;
                       case '/':
                        t.push(left / right);
                 }
              }
              else
              {
                 t.push(stoi(tokens[i]));
              }
          }
          return t.top();
    }
};

到了这里，关于【leetcode C++】逆波兰表达式求值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！