题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
代码说话：双栈的思路
我觉得精解的双栈思路有点复杂，简化一下：
分模块：1.处理数字
2.遇到‘（’时要进行的操作是将其放入操作符栈，然后确认下一个符号位是不是为负号，是则将0先压入数据栈，再将负号压入操作符栈
3.遇到‘）’时计算栈内所有的东西，直到遇到左括号为止
4.当遇到其他操作符时，先判断当前的操作符是否小于栈顶的操作符，如果是，那么此时则需要将栈的结果计算后，重新放入栈中，同样的，当前的操作符仍需入栈
举例：2*3 - 4，符号的优先级低于*，所以此时要将2*3优先计算出来，然后将数字6放入数据栈中，同时操作符‘-’也要入栈。
5.最后返回栈顶的值即可
注：只有在遇到左括号以及加减乘除的操作符时才有可能调用计算函数，不然的话暂时不需要计算
class Solution {
public:
map<char, int> m_map = {{'-', 1},{'+', 1},{'*', 2},{'/', 2},{'%', 2}};
stack<char> stack1;//存放特殊操作符
stack<int> stack2;//存放数字
void cal()
{
//处理边界条件
if(stack2.empty() || stack2.size() < 2) return ;
if(stack1.empty()) return;
long int res;
char s = stack1.top(); stack1.pop();
int a = stack2.top();stack2.pop();
int b = stack2.top();stack2.pop();
switch(s)
{
case '-': res = b - a;break;
case '+': res = b+a;break;
case '*': res = a*b;break;
case '/': res = b/a;break;
}
stack2.push(res);
}
int solve(string s) {
//同一级可以直接算,遇到括号后的第一个运算符可以先补0；
int temp = 0;
stack2.push(0);
for(int i = 0; i < s.size(); i++)
{ if(isdigit(s[i]))
{
temp = 10*temp + (s[i] - '0');
while(i + 1<s.size() && isdigit(s[i+1]))
{
i++;
temp = 10*temp + (s[i] - '0');
}
stack2.push(temp);
temp = 0;
}
else if('(' == s[i])
{
stack1.push(s[i]);
if(i + 1<s.size() && '-' == s[i+1])
{
stack2.push(0);
stack1.push('-');
i++;
}
}
else if(')' == s[i])
{
//开始计算栈内的东西，直到遇到了‘）’,如何处理优先级的问题
while(stack1.top() != '(')
{
cal();
}
stack1.pop();
}
else if('+' == s[i] ||'-' == s[i] || '*' == s[i] || '/' == s[i])
{
//在这里把能算的都算进去,TBD
while(!stack1.empty() && stack1.top() != '(' && m_map[s[i]] <= m_map[stack1.top()])
{
cal();
}
stack1.push(s[i]);
}
else{}
}
while(!stack1.empty()) cal();
return stack2.top();
}
};
