中缀表达式转后缀表达式。对于普通中缀表达式的计算,我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈,扫描该中缀表达式:
- 如果遇到数字,直接将该数字输出到后缀表达式(以下部分用「输出」表示输出到后缀表达式);
- 如果遇到左括号,入栈;
- 如果遇到右括号,不断输出栈顶元素,直至遇到左括号(左括号出栈,但不输出);
- 如果遇到其他运算符,不断去除栈顶所有运算优先级大于等于当前运算符的运算符,输出。最后,新的符号入栈;
- 把栈中剩下的符号依次输出,表达式转换结束。
对于一个后缀表达式,只需要 维护一个数字栈,每次遇到一个运算符,就取出两个栈顶元素,将运算结果重新压入栈中 。最后,栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度 。
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; } };