表达式求值

中缀表达式转后缀表达式。对于普通中缀表达式的计算,我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈,扫描该中缀表达式:

  1. 如果遇到数字,直接将该数字输出到后缀表达式(以下部分用「输出」表示输出到后缀表达式);
  2. 如果遇到左括号,入栈;
  3. 如果遇到右括号,不断输出栈顶元素,直至遇到左括号(左括号出栈,但不输出);
  4. 如果遇到其他运算符,不断去除栈顶所有运算优先级大于等于当前运算符的运算符,输出。最后,新的符号入栈;
  5. 把栈中剩下的符号依次输出,表达式转换结束。

对于一个后缀表达式,只需要 维护一个数字栈,每次遇到一个运算符,就取出两个栈顶元素,将运算结果重新压入栈中 。最后,栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度  。

class Solution {
    //适用于个位数,加减乘除
public:
    int calculate(string s) {
        stack<char> sign;//运算符栈
        vector<char> postfix;//后缀表达式
        for (auto ch :s) {
            if (ch == ' ')
                continue;
            else if (isdigit(ch)) {
                postfix.push_back(ch);
            } else if (ch == '(') {
                sign.push(ch);
            } else if (ch == ')') {
                while (!sign.empty() && sign.top() != '(') {
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.pop();
            } else {
                while (!sign.empty() && get_priority(sign.top()) >= get_priority(ch)) {//只要栈顶运算符的优先级不低于新运算符,就不断取出栈顶并输出
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.push(ch);
            }
        }
        while (!sign.empty()) {
            postfix.push_back(sign.top());
            sign.pop();
        }
        //遇到运算符就计算
        stack<int> nums;
        for (auto item:postfix) {
            if (isdigit(item))
                nums.push(item - '0');
            else {
                int one = nums.top();
                nums.pop();
                int two = nums.top();
                nums.pop();
                if (item == '+') {
                    nums.push(one + two);
                } else if (item == '-') {
                    nums.push(two - one);
                } else if (item == '*') {
                    nums.push(one * two);
                } else if (item == '/') {
                    nums.push(two / one);
                }
            }

        }
        return nums.top();
    }

    int get_priority(char ch) {
        if (ch == '+' || ch == '-')
            return 0;
        else if (ch == '*' || ch == '/')
            return 1;
        else
            return -1;
    }
};
0