/* 将中缀表达式(a+b)转换为后缀表达式(ab+)的算法思想：
·当读到数字直接送至输出队列中
·当读到运算符t时，
a.将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中；
b.t进栈
·读到左括号时总是将它压入栈中
·读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。
运用后缀表达式进行计算的具体做法：
·建立一个栈S
·从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中
·如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束 */
#include <iostream>
#include <string>
using namespace std;
char ex[100];//存储后缀表达式
char str[100];//存储算术表达式
char stack[100];//作为栈使用
char ch;//当前判断的字符
int i=0;//i为算术表达式str的下标
int t;//t为后缀式ex的下标
int top=0;//top为栈顶
void trans();//转换函数
void compute();//计算后缀式的值
void trans()//将中缀式转换为后缀式
{
cout<<"输入一个算术表达式，以#号结束："<<endl;
while(str[i]!='#')//中缀式以#号结束
{
i++;//因为i的初值设为0
cin>>str[i];
}
//开始扫描
t=1;
i=1;
ch=str[i];
i++;//i指向当前扫描字符的下一位
while(ch!='#')//逐个扫描，直至遇到#号结束
{
switch(ch)
{
case'('://遇到（，进栈
top++;
stack[top]=ch;
break;
case')'://遇到），将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至后缀式队列后，再丢弃左括号。
while(stack[top]!='(')
{
ex[t]=stack[top];
top--;
t++;
}
top--;//丢弃（
break;
case'+':
case'-':
while(top!=0 && stack[top]!='(')
{
ex[t]=stack[top];
top--;
t++;
}
top++;//因为top的初值为0
stack[top]=ch;
break;
case'*':
case'/':
while(stack[top]=='*'|| stack[top]=='/')
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
/*注意！除操作数外，其它符号都要用到栈*/
default:while(ch>='0' && ch<='9')//遇到操作数直接送至后缀式队列
{
ex[t]=ch;
t++;
ch=str[i];
i++;//此时i指向操作数之后的运算符的后一位！！
}
i--;//要在操作数之后，运算符之前添加空格符
ex[t]=' ';//用空格符隔开
t++;
}//switch结束
ch=str[i];//仿照default中的，返回添加空格符之前的操作
i++;
}//结束while
while(top!=0)//仍有运算符在栈中
{
ex[t]=stack[top];
t++;
top--;
}
ex[t]=' ';//不能省，若省掉则无法进入compute函数??
for(int j=1;j<i-1;j++)
cout<<str[j];
cout<<"的后缀式为：";
for(j=1;j<t;j++)
cout<<ex[j];
}
void compute()
{
float stack[100];//作为栈使用
int d;//用于存放当前的计算结果
char ch;
int t=1;
int top =0;
ch=ex[t];
t++;
while(ch!=' ')//此空格符为后缀式中的最后一个字符，与上文中的" ex[t]=' '; "相对应
{
switch(ch)
{
case'+':
stack[top-1]=stack[top-1]+stack[top];
top--;
break;
case'-':
stack[top-1]=stack[top-1]-stack[top];
top--;
break;
case'*':
stack[top-1]=stack[top-1]*stack[top];
top--;
break;
case'/':
if(stack[top]!=0)
stack[top-1]=stack[top-1]/stack[top];
else
{
cout<<"\n除零错误!"<<endl;
exit(0);//异常退出
}
top--;//两个操作数算出一个结果存放到栈顶，那两操作数便可丢弃，故top-1
break;
default:
d=0;
while(ch>='0' && ch<='9')
{
d=10*d+ch-'0';//将数字字符转化为对应的数值，*10是与大于10的数值时要进位
ch=ex[t];
t++;
}
top++;
stack[top]=d;//栈顶存放当前计算结果
}//switch结束
ch=ex[t];//跳过空格符，扫描下一个运算符或操作数
t++;
}
cout<<"\n计算结果为:"<<stack[top]<<endl;
}
void main()
{
trans();
compute();
}
结果如图所示：
