【题目描述】
为了便于处理表达式,常常将普通表达式(称为中缀表示)转换为后缀{运算符在后,如X/Y写为XY/表达式。在这样的表示中可以不用括号即可确定求值的顺序,如:(P+Q)*(R-S) → PQ+RS-*。后缀表达式的处理过程如下:扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即为该后缀表达式的值。
输入一个中缀表达式,编程输出其后缀表达式,要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见,假设输入的中缀表达式由+(加)、-(减)、×(乘)、/(除)四个运算符号以及左右圆括号和大写英文字母组成,其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过200个字符,且都是正确的,即没有语法错误,并且凡出现括号其内部一定有表达式,即内部至少有一个运算符号。
【输入格式】
只有一行,为中缀表达式
【输出格式】
只有一行,为转换后的后缀表达式
【样例输入】
X+A*(Y-B)-Z/F
【样例输出】
XAYB-*+ZF/-
【问题分析】
通过上面分析,我们不难得出以下结论:
中缀表达式转后缀表达式遵循以下原则:
1.遇到操作数,直接输出;
2.栈为空时,遇到运算符,入栈;
3.遇到左括号,将其入栈;
4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;
5.遇到其他运算符'+''-''*''/'时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;
6.最终将栈中的元素依次出栈,输出。
经过上面的步骤,得到的输出既是转换得到的后缀表达式。
c++代码:
#include<iostream> #include<cstring> #include<stack> #include<cstdio> using namespace std; string s; stack<char> a; bool isoperator(char);//判断是否为运算符 int getpre(char,bool);//判断运算符的优先级别 void work(); int main() { cin>>s; work(); return 0; } void work() { int i; for(i=0;i<s.size();++i)//逐一枚举每一个字符 { if(!isoperator(s[i]))//如果不是运算符直接输出 { cout<<s[i]; continue; } else//如果是运算符执行下面语句 { if(a.empty())//如果当前栈为空,直接把运算符入栈 { a.push(s[i]); continue; } else//如果栈非空执行下面语句 { if(s[i]==')')//如果是')'把栈里的运算符依次输出,直到遇到'('为止 { while(a.top()!='('&& !a.empty()) { cout<<a.top(); a.pop(); } a.pop();//把栈里的'('直接出栈 continue; } while(!a.empty()&&getpre(s[i],false)<=getpre(a.top(),true)) {//如果运算符小于等于栈顶元素,依次输出栈顶运算符,直到栈为空或 //栈顶元素优先级别低于当前运算符,此处有个坑爹的地方是一定要注意 // !a.empty()条件写在前面,否则可能报错,因为getpre函数有对栈顶 //元素操作,如果栈为空则栈顶元素是无法访问,会出错,记住条件判断 //是从左至右依次判断,只要一个不成立,后面就不会判断 cout<<a.top(); a.pop(); } a.push(s[i]);//把当前运算符入栈 } } } while(!a.empty())//依次输出栈里剩余运算符 { cout<<a.top(); a.pop(); } } bool isoperator(char ch) { if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='(')return true; else return false; } int getpre(char ch,bool flag) { if(ch=='+'||ch=='-') return 1; if(ch=='*'||ch=='/') return 2; if(ch=='('&&flag) return 0;//当'('在栈里的时候优先级设为0 if(ch=='('&&!flag) return 3;//当'('不在栈里的时候优先级设为3 }