算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式说明:
输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。
输出格式说明:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。
样例输入与输出:
序号 | 输入 | 输出 |
1 |
2+3*(7-4)+8/4 |
2 3 7 4 - * + 8 4 / + |
2 |
((2+3)*4-(8+2))/5 |
2 3 + 4 * 8 2 + - 5 / |
3 |
1314+25.5*12 |
1314 25.5 12 * + |
4 |
-2*(+3) |
-2 3 * |
5 |
123 |
123 |
#include<iostream> #include<stack> #include<string.h> using namespace std; stack<char> s; int Judge(char a) { if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)||(a==‘(‘)||(a==‘)‘)) return 1; return 0; } int Judge_(char b,char a) { if(b==‘+‘||b==‘-‘) if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)||(a==‘(‘)) return 1; return 0; } int Judge_jjcc(char a) { if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)) return 1; return 0; } int Judge_jj(char a) { if((a==‘+‘)||(a==‘-‘)) return 1; return 0; } int premer(char a,char b) { switch(a) { case ‘+‘: { switch(b) { case ‘+‘:return 0;break; case ‘-‘:return 0;break; case ‘*‘:return 0;break; case ‘/‘:return 0;break; case ‘(‘:return 0;break; } }break; case‘-‘: { switch(b) { case ‘+‘:return 0;break; case ‘-‘:return 0;break; case ‘*‘:return 0;break; case ‘/‘:return 0;break; case ‘(‘:return 0;break; } }break; case ‘*‘: { switch(b) { case ‘+‘:return 1;break; case ‘-‘:return 1;break; case ‘*‘:return 0;break; case ‘/‘:return 0;break; case ‘(‘:return 0;break; } }break; case‘/‘: { switch(b) { case ‘+‘:return 1;break; case ‘-‘:return 1;break; case ‘*‘:return 0;break; case ‘/‘:return 0;break; case ‘(‘:return 0;break; } }break; case‘(‘: { switch(b) { case ‘+‘:return 0;break; case ‘-‘:return 0;break; case ‘*‘:return 0;break; case ‘/‘:return 0;break; case ‘(‘:return 0;break; } }break; default:break; } } int main() { char a[30]; scanf("%s",a); int len=strlen(a); int con_flag=0; int op_flag=1; bool first=false; for(int i=0;i<len;i++) { if(Judge(a[i])&&(!(i==0&&Judge_jj(a[i])))&&(!Judge_(a[i],a[i-1]))) //正常符号 { if(a[i]==‘)‘) { while(s.top()!=‘(‘) { char temp=s.top(); s.pop(); cout<<" "<<temp; } s.pop(); while(!s.empty()&&s.top()!=‘(‘) { char temp_t=s.top(); s.pop(); cout<<" "<<temp_t; } } else if(!s.empty()&&(a[i]!=‘(‘)) { if(premer(s.top(),a[i])) con_flag=1; else con_flag=0; while(con_flag)//压入的操作符优先级要大于顶部元素 { char temp2=s.top(); cout<<" "<<temp2; s.pop(); if(!s.empty()) { if(premer(s.top(),a[i])) con_flag=1; else con_flag=0; } else con_flag=0; } s.push(a[i]); } else s.push(a[i]); if(first==false&&Judge_jjcc(a[i])) { first=true; cout<<" "; } } else if(a[i]==‘+‘||a[i]==‘-‘)//表示数据的正负 { if(a[i]==‘-‘) op_flag*=-1; //是-号 后面的数字乘以-1; //否则忽略 first=true; } else { if(i==0) { cout<<a[i]; } else { if(op_flag==-1) { cout<<‘-‘<<a[i]; op_flag=1; } else cout<<a[i]; first=false;//遇到数字 } } } while(!s.empty()) { cout<<" "<<s.top(); s.pop(); } //printf("%s",a); system("pause"); return 0; }
解题报告:
对于取进来的字符可以分成3种情况
【1】正常操作符 表示运算关系
【2】正负号 表示数据的正负 如+2*(-2) 注意:本题中+号表示数据的正负时不输出 所以只要考虑‘-’的情况
【3】正常数字
【特殊情况】:判断第一个字符,之所以要考虑第一个字符是因为在字符a[i]的情况下判断情况【2】的状态时要查看a[i-1],如果是第一个字符 i=0,且a[i]==‘+‘或者a[i]==‘-‘归到【2】,如果是数字归到【3】,如果是正常操作符归到【1】。
输出格式考虑:考虑一种特殊情况,1234···连续的数字。思路:第一次碰到【1】正常操作符入队列的时候输出一个空格。每次弹出操作符都先输出一个空格。
原文:http://blog.csdn.net/linsheng9731/article/details/22619447