蓝桥杯表达式计算 By Assassin

2019-11-10 20:00:13

字体：大中小

来源：转载

供稿：网友

具体的分析讲解可以看我的博客如下

利用栈实现表达式讲解链接

下面直接上代码，具体的分析在代码的注释中了~我是用string实现的~

#include<bits/stdc++.h>using namespace std;stack<char>sign; //记录符号 queue<string>exchange; //记录中缀式转换为后缀式的输出 stack<int>number; //以int形势记录后缀式计算时的值 int stackout(char c){ //栈外符号优先级值 if(c=='(') return 7; else if(c=='*'||c=='/') return 5; else if(c=='+'||c=='-') return 3; else if(c==')') return 1;}int stackin(char c){ //栈内符号优先级值 if(c=='(') return 1; else if(c=='*'||c=='/') return 5; else if(c=='+'||c=='-') return 3; else if(c==')') return 7;}int string_to_int(string s){ //string型转int型 int ans=0; for(int i=0;i<s.size();i++){ ans=ans*10+(s[i]-'0'); } return ans;}int calc(string s){ string tmp=""; //记录多位数的字符串 for(int i=0;i<s.size();i++){ if(s[i]>='0'&&s[i]<='9'){ //如果是字符，说明是数的一部分 tmp+=s[i]; } else { if(tmp!=""){ //必须有这个，因为可能出现*(这种情况，这个时候tmp是空的 exchange.push(tmp); tmp=""; } if(s[i]=='('){ //如果是(入栈 sign.push(s[i]); } else if(s[i]==')'){ //如果是)一直出栈到(出现 while(sign.top()!='('){ string zc=""; zc+=sign.top(); //char转到string exchange.push(zc); sign.pop(); } sign.pop(); //弹出(，这个(是不出现在表达式中的 } else { if(sign.empty()){ //初始时如果栈是空的，不管是什么直接入栈 sign.push(s[i]); continue; } int sign1,sign2; sign1=stackout(s[i]); //计算当前比较字符的栈外优先级值 sign2=stackin(sign.top()); //计算栈顶比较字符的栈内优先级值 if(sign1<=sign2){ //当栈外值较小时 int sign3; string zc=""; //比较过了直接弹出记录 zc+=sign.top(); exchange.push(zc); sign.pop(); while(!sign.empty()){ //继续弹出记录 sign3=stackin(sign.top()); if(sign3<=sign2) break; //直到出现大于栈顶操作符的优先级结束，注意现在都是和栈顶比的！！！ zc.clear(); zc+=sign.top(); exchange.push(zc); sign.pop(); } sign.push(s[i]); //记着把栈外的入栈 } else{ sign.push(s[i]); //当栈外的优先级值大的时候直接入栈 } } } } if(tmp!=""){ //最后一个数进入后缀表达式 exchange.push(tmp); } while(!sign.empty()){ //未弹出的符号进入后缀表达式 string zc=""; zc+=sign.top(); exchange.push(zc); sign.pop(); } //计算后缀表达式了 while(!exchange.empty()){ tmp=exchange.front(); exchange.pop(); if(tmp[0]>='0'&&tmp[0]<='9'){ //是数字转换后进入number中 number.push(string_to_int(tmp)); } else { int key,number1,number2; number2=number.top(); //注意number1和number2的顺序！ number.pop(); number1=number.top(); number.pop(); if(tmp=="+") key=number1+number2; if(tmp=="-") key=number1-number2; if(tmp=="*") key=number1*number2; if(tmp=="/") key=number1/number2; number.push(key); //计算完了入栈 } } cout<<number.top()<<endl; //剩下的最后一个就是结果 }int main(){ //freopen("input.txt","r",stdin); string s; while(cin>>s){ calc(s); } return 0;}

上一篇：C实例---进制转换（栈实现）

下一篇：Database,Uva1592