首页 > 代码库 > 蓝桥杯_表达式计算
蓝桥杯_表达式计算
这道题的关键是中缀表达式转后缀表达式。
定义一个符号栈和一个数字栈。怎么中缀转后缀,数据结构这本书上有。
这里简单说一下,从左往右扫描字符串,遇见数字就压入数字栈。
遇见符号的话,
1、如果是‘(‘,直接入栈。
2、如果是‘)‘,挨个弹出栈顶元素,直到遇见‘(‘停止,但要把‘(‘弹出来。
3、其他符号,只要栈顶符号的优先级大于等于自己,就弹出。然后再入栈。
按照书上的过程走。中缀转后缀的过程中,每次符号栈弹出一个符号,就进行运算,当转换完了,计算也就完了。
下面看代码:
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; string exp; //输入的表达式 stack<char> s; //符号栈 stack<int> num; //数字栈 int calc(int a,int b,char c) //a,b是操作数,c是操作符,返回结果 { int res=0; switch(c) { case ‘+‘: res=a+b; break; case ‘-‘: res=a-b; break; case ‘*‘: res=a*b; break; case ‘/‘: res=a/b; break; } return res; } void compute(char c) //每次符号栈输出一个符号,在这里计算 { int a=0,b=0; if(!num.empty()) { b=num.top(); //先弹出的是b num.pop(); if(!num.empty()) { a=num.top(); num.pop(); } } int res=calc(a,b,c); num.push(res); //把弹出的两个数的计算结果 入栈。 } void midTolast(string exp) //中缀转后缀表达式 同时计算。 { while(!s.empty()) s.pop(); string number=""; // for(int i=0; i<exp.length(); i++) { if(exp[i]>=‘0‘&&exp[i]<=‘9‘) { number+=exp[i]; continue; } if(number!="") { num.push(atoi(number.c_str())); //如果有数字则入数字栈 atoi函数的作用是字符串转数字。 } number.clear(); //清空数字字符串 if(exp[i]==‘(‘) //如果是‘(‘直接入符号栈 { s.push(exp[i]); } else if(exp[i]==‘)‘) //碰见‘)‘,符号栈的元素依次弹出,直到遇见‘(‘。 { while(!s.empty()) { char temp=s.top(); if(temp==‘(‘) //如果是‘(‘只出栈不输出 { s.pop(); break; } else { compute(temp); //否则计算符号栈弹出的每个操作符。 s.pop(); } } } else if(exp[i]==‘+‘||exp[i]==‘-‘) //如果是‘+‘,‘-‘。把符号栈内大于等于自己优先级的符号弹出。 { while(!s.empty()) { if(s.top()==‘(‘) //因为‘(‘最低,‘+‘,‘-‘仅次于它,遇见‘(‘停止出栈 break; else { compute(s.top()); //计算弹出的每个操作符 s.pop(); } } s.push(exp[i]); //把大于等于自己的符号弹出之后 自己入栈。 } else if(exp[i]==‘*‘||exp[i]==‘/‘) //如果是‘*‘,‘/‘ { while(!s.empty()) { if(s.top()==‘+‘||s.top()==‘-‘||s.top()==‘(‘) break; //遇见比自己优先级低的则停止出栈 else //否则,出栈 { compute(s.top()); s.pop(); } } s.push(exp[i]); //之后入栈 } } while(!s.empty()) //把剩下的符号挨个弹出 { compute(s.top()); s.pop(); } cout<<num.top()<<endl; //输出结果 } int main() { while(cin>>exp) { midTolast(exp); } return 0; }
蓝桥杯_表达式计算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。