题目

image.png

思路

  • 本质就是模拟四则运算
  • 需要维护两个栈，op放操作符，nn放数字，无论什么操作，一定是1个操作符匹配2个数字，所以说，独立出来的运算函数一定是简单的，操作符栈顶弹1个，数字栈顶弹2个，算完了再压进去。
  • 如何维护括号的优先级，遇到左括号直接压栈，遇到右括号就一直操作直到左括号。这一步很关键，体现了“局部优先”的思想。

  • 最后将操作栈清空，剩下的数字栈的栈顶就是需要的数字。

    代码

    1. class Solution {
    2. public:
    3.   void calcu(stack<char>& op, stack<int>& nn) {
    4.       if (op.empty() || nn.empty()) {
    5.           return;
    6.       }
    8.       char cur_op = op.top();
    9.       op.pop();
    10.       if (cur_op == '(') {
    11.           return;
    12.       }
    14.       int num_behind = nn.top();
    15.       nn.pop();
    16.       int num_forward = nn.top();
    17.       nn.pop();
    19.       int res_num = 0;
    20.       if (cur_op == '*') {
    21.           res_num = num_forward * num_behind;
    22.       } else if (cur_op == '+') {
    23.           res_num = num_forward + num_behind;
    24.       } else if (cur_op == '-') {
    25.           res_num = num_forward - num_behind;
    26.       } else if (cur_op == '/') {
    27.           res_num = num_forward / num_behind;
    28.       }
    30.       nn.push(res_num);
    31.   }
    33.   int calculate(string s) {
    34.       stack<char> op;
    35.       stack<int> nn;
    37.       map<char, int> h = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    38.       int len_s = s.size();
    39.       for (int i = 0; i < len_s; ++i) {
    40.           if (s[i] == ' ') {
    41.               continue;
    42.           }
    44.           if (isdigit(s[i])) {
    45.               int j = i + 1, num = int (s[i] - '0');
    46.               while (j < len_s && isdigit(s[j])) {
    47.                   num *= 10;
    48.                   num += int (s[j] - '0');
    49.                   j++;
    50.               }
    51.               nn.push(num);
    52.               i = j - 1;
    53.           } else if (s[i] == '(') {
    54.               op.push(s[i]);
    55.           } else if (s[i] == ')') {
    56.               while (!op.empty() && op.top() != '(') {
    57.                   calcu(op, nn);
    58.               }
    59.               // 左括号也要出栈
    60.               op.pop();
    61.           } else {
    62.               // 低优先级入栈需要先将高优先级弹栈
    63.               while (!op.empty() && h[op.top()] >= h[s[i]]) {
    64.                   cout << s[i] << endl;
    65.                   calcu(op, nn);
    66.               }
    67.               op.push(s[i]);
    68.           }
    69.       }
    71.       while (!op.empty()) {
    72.           calcu(op, nn);
    73.       }
    74.       return nn.top();
    75.   }
    76. };