本文共 3047 字，大约阅读时间需要 10 分钟。

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

Example 1:

Input: s = "3+2*2"Output: 7

Example 2:

Input: s = " 3/2 "Output: 1

Example 3:

Input: s = " 3+5 / 2 "Output: 5

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 231 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

题意：实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+，- ，*，/ 四种运算符和空格。整数除法仅保留整数部分。

解法1 逆波兰表达式+符号栈+数值栈

先去除字符串表达式中的空格，再分割成 token 序列。最后使用符号栈和数值栈，将 token 序列边处理为逆波兰形式，边求值。具体代码如下：

class Solution {
   private:    vector
   
     tokens;    unordered_map
    
      rec = {
   {
   '+', 0}, {
   '-', 0}, {
   '*', 1}, {
   '/', 1}};    function
     
       eval = [](int a, char op, int b) {
           return (op == '+' ? (a + b) : (op == '-' ? (a - b) : (op == '*' ? (a * b) : (a / b))));    };    void split(const string &s, const string &delim) {
           tokens.clear();        size_t beginPos = s.find_first_not_of(delim);        size_t endPos = s.find_first_of(delim, beginPos);        while (beginPos != string::npos) {
               tokens.push_back(s.substr(beginPos, endPos - beginPos)); //分割词序列            if (endPos != string::npos) tokens.push_back(string(1, s[endPos])); //运算符号            beginPos = s.find_first_not_of(delim, endPos);            endPos = s.find_first_of(delim, beginPos);        }    }    int procAndCalc() {
               stack
      
        nums;        stack
       
         ops;        int n = tokens.size();        for (int i = 0; i < n; ++i) {
               switch (tokens[i][0]) {
                   case '+':                 case '-':                case '*':                case '/':                     while (!ops.empty() && rec[tokens[i][0]] <= rec[ops.top()]) {
    //优先级更低,计算高优先级的运算符                        int b = nums.top(); nums.pop();                        int a = nums.top(); nums.pop();                        char op = ops.top(); ops.pop();                        nums.push(eval(a, op, b));                    }                    ops.push(tokens[i][0]);                    break;                default:                     nums.push(stoi(tokens[i]));                     break;            }        }        while (!ops.empty()) {
               int b = nums.top(); nums.pop();            int a = nums.top(); nums.pop();            char op = ops.top(); ops.pop();            nums.push(eval(a, op, b));             }        return nums.top();    }public:    int calculate(string s) {
            string str;        for (const char &c : s) if (c != ' ') str.push_back(c); //删除所有空格        split(s, "+-*/"); //得到token序列;s中的整数都是非负整数,不然处理负数就很麻烦,不如直接扫描字符串        return procAndCalc(); //处理得到数值栈和符号栈,同时计算结果    }};
       
      
     
    
   

运行效率如下：

执行用时：108 ms, 在所有 C++ 提交中击败了6.41% 的用户内存消耗：25.2 MB, 在所有 C++ 提交中击败了5.04% 的用户

下次写一下只使用一个数值栈的做法。

转载地址：https://memcpy0.blog.csdn.net/article/details/111691196 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！