题目描述
> 输入一个表达式(用字符串表示),求这个表达式的值。 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’, ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
这是一道简单题??? 1、将所有的括号都换成小括号; 2、设置符号栈和数字栈 3、设置函数cal(),对数字栈栈顶的两个元素和符号栈栈顶的一个元素进行运算(注意顺序) 输入遇到前括号- push入符号栈;判断下一位如果是也是符号,则先往数字栈中push一个0; 输入遇到后括号- 直到遇到前括号前,一直进行cal()计算,算出括号内的答案后push入数字栈;此时括号内栈从下往上看优先级是递增的,直接按出栈顺序直接计算后入栈。 输入遇到数字- 向后判断这个数字有多长,截取字符串转换成数字放入数字栈; 输入遇到+-*/符号- 判断该符号与符号栈栈顶符号的优先级,当小于等于的时候进行cal,然后再入栈,否则直接入符号栈。小于是当出现先乘除后加减的情况,等于表示同级运算,应该从左向右,所以先计算栈里的。注意这里是while循环。 4、最后结束循环化,对栈再进行一次while的cal(),输出最后留下的唯一的栈顶。 5、但凡需要循环,判断条件都要注意此时是否是空栈。
#include<iostream>
#include<vector>
#include<stack>
#include <string>
#include <map>
using namespace std;
bool isdigital(char a) {
return ('0' <= a && a <= '9') ? true : false;
}
void cal(stack<int>& num, stack<char>& symbol) {//取出数字栈顶的两个元素和符号栈顶的一个符号进行运算
int a = num.top();
num.pop();
int b = num.top();
num.pop();
char c = symbol.top();
symbol.pop();
int ans;
switch (c) {//一定要注意是b对a操作
case '+': {ans = b + a; break; }
case '-': {ans = b - a; break; }
case '*': {ans = b * a; break; }
case '/': {ans = b / a; break; }
}
num.push(ans);//计算结果放回栈中
}
int main() {
string s;
cin >> s;
map<char, int> grade;
grade['('] = 0; grade[')'] = 0; grade['+'] = 1; grade['-'] = 1; grade['*'] = 2; grade['/'] = 2;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '{' || s[i] == '[') s[i] = '(';
if (s[i] == '}' || s[i] == ']') s[i] = ')';
}
stack<int> num;
stack<char> symbol;
if (!isdigital(s[0])) num.push(0);//避免-5*4这种上来就是符号的
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {//如果是左括号,入符号栈
symbol.push('(');
if (!isdigital(s[i + 1]))//避免(-4+5)这样的情况出现,所以入0
num.push(0);
}
else if (s[i] == ')') {//遇到后括号,则将该括号内式子计算出来
while (symbol.top() != '(')
cal(num, symbol);//计算括号里的
symbol.pop();//左括号弹出
}
else if (isdigital(s[i])) {//遇到数字,提取出完整的数字放入数字栈
int left = i;
while (i + 1 < s.length() && isdigital(s[i + 1])) i++;
num.push(stoi(s.substr(left, i - left + 1)));//也可以ans=ans*10+s[i]算出来
}
else //如果是+-*/,当s[i]的优先级小于等于栈顶符号优先级时,对栈顶进行一次计算,直到不符合条件
{
while (!symbol.empty() && grade[s[i]] <= grade[symbol.top()])//注意这里是while不是if,如9-5*4+5;
cal(num, symbol);
symbol.push(s[i]);
}
}
while (!symbol.empty())
cal(num, symbol);
cout << num.top();
}
```</char></int></char,></char></int></map></string></stack></vector></iostream>