中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3；
后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *；
前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：* + 2 1 3。
实验目的
1.熟悉栈的应用
2.熟悉中缀表达式向前缀的转化
实验内容
1.编写程序实现中缀表达式向前缀的转化
如： 2*3/(2-1)+5*(4-1)转化后为+/*23-21*5-41
// 中缀转前缀/*
参考算法
1）求输入串的逆序。
2）检查输入的下一元素。
3）假如是操作数，把它添加到输出串中。
4）假如是闭括号，将它压栈。
5）假如是运算符，则
i)假如栈空，此运算符入栈。
ii)假如栈顶是闭括号，此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。
iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。
6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
7）假如输入还未完毕，跳转到步骤2。
8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
9）求输出串的逆序。*/
- #include<iostream>
- #include<string>
- using namespace std;
- char stack[50];//定义顺序栈，其中第一个元素表示栈为空；
- int top=0;//栈顶指针，为0表示栈为空；
- int level(char op)//判断运算符级别函数；其中* /的级别为2，+ -的级别为1；
- {
- int level;
- switch(op)
- {
- case'+':
- case'-':level=1; break;
- case'*':
- case'/':level=2; break;
- default:level=0;break;
- }
- return level;
- }
- bool isOperator(char op)//判断输入串中的字符是不是操作符，如果是返回true
- {
- if(op=='+'||op=='-'||op=='*'||op=='/')
- return true;
- else
- return false;
- }
- string convert(string s)//将一个中缀串转换为后缀串，
- {
- string output="";//输出串
- for(int i=s.length()-1;i>=0;)//1）求输入串的逆序。
- {
- if(s[i]>=48&&s[i]<=57)
- output=output+s[i];//3）假如是操作数，把它添加到输出串中。
- if(s[i]==')')//4）假如是闭括号，将它压栈。
- {
- top++;
- stack[top]=s[i];
- }
- while(isOperator(s[i]))//如果是运算符，执行算法(5)对应操作；
- {
- if(top==0||stack[top]==')'||level(s[i])>=level(stack[top]))
- {
- top++;
- stack[top]=s[i];
- break;
- }
- else
- {
- output=output+stack[top];
- top--;
- }
- }
- if(s[i]=='(')//6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
- {
- while(stack[top]!=')')
- {
- output=output+stack[top];
- top--;
- }
- top--;
- }
- i--;//7）假如输入还未完毕，跳转到步骤2。
- }
- while(top!=0)//8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
- {
- output=output+stack[top];
- top--;
- }
- return output;
- }
- int main()
- {
- string input,output;
- cout<<"请输入串:";
- cin>>input;
- output=convert(input);
- cout<<"后缀串为:";
- for(int i=output.length()-1;i>=0;i--)//9）求输出串的逆序。
- cout<<output[i];
- cout<<endl;
- return 0;
- }