（3）如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为存放结果（逆波兰式）的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
下面以(a+b)*c为例子进行说明：
(a+b)*c的逆波兰式为ab+c*，假设计算机把ab+c*按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理，那么ab+c*的执行结果如下：
（1）a入栈（0位置）
（2）b入栈（1位置）
（3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）
（4）c入栈（1位置）
（5）遇到运算符“*”，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈（0位置）
经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。
算法用到三个栈：a栈，b栈，in栈。
pop（in）为输入栈栈顶元素出栈，pop（a，Q）为Q入a栈，NEXT算法即为进行下一轮循环，其中ω1
算法开始时，现将△如b栈，输入栈以#号结尾。
输入流 b[s-1] | 名字Q | ( | ω2 | ) | # |
△ | POP(in); PUSH(a，Q) NEXT | POP(in); PUSH(b，△) NEXT | POP(in) PUSH(b，ω2) NEXT | POP(in) POP(b，B) NEXT | STOP |
ω1 | POP(in) PUSH(a，Q) NEXT | POP(in) PUSH(b，△) NEXT | 若ω1 POP(in) PUSH(b，ω2) NEXT 若ω1≥ω2，则POP(in) POP(b，B）， PUSH(a,B) | POP(b，B) PUSH(a，B) | POP(b，B) PUSH(a，B) |
//#include<iostream>
#include <stdlib.h>
#include <stdio.h>
#include <stack>
#include <math.h>
#include <string.h>
#definemax100
usingnamespacestd;
char ex[max]; /*存储后缀表达式*/
voidtrans()
{ /*将算术表达式转化为后缀表达式*/
char str[max]; /*存储原算术表达式*/
char stack[max]; /*作为栈使用*/
char ch;
int sum, i, j, t, top = 0;
printf("*****************************************\n");
printf("*输入一个求值的表达式，以#结束。*\n");
printf("******************************************\n");
printf("算数表达式：");
i = 0; /*获取用户输入的表达式*/
do
{
i++;
//cin>>str[i];/*此步我用的是C++C语言的话在后面之所以用这个有一点区别都*/
scanf("%c", &str[i]);
} while (str[i] != '#' && i != max);
sum = i;
t = 1;
i = 1;
ch = str[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++;
stack[top] = ch;
break;
case '*': /*判定为乘除号*/
case '/':
while (stack[top] == '*' || stack[top] == '/')
{
ex[t] = stack[top];
top--;
t++;
}
top++;
stack[top] = ch;
break;
case'':
break;
default:
while (ch >= '0' && ch <= '9')
{ /*判定为数字*/
ex[t] = ch;
t++;
ch = str[i];
i++;
}
i--;
ex[t] ='';
t++;
}
ch = str[i];
i++;
}
while (top != 0)
{
ex[t] = stack[top];
t++;
top--;
}
ex[t] ='';
printf("\n\t原来表达式：");
for (j = 1; j < sum; j++)
printf("%c", str[j]);
printf("\n\t逆波兰式：", ex);
for (j = 1; j < t; j++)
printf("%c", ex[j]);
}
voidcompvalue()
{ /*计算后缀表达式的值*/
floatstack[max], d; /*作为栈使用*/
charch;
intt = 1, top = 0; /*t为ex下标，top为stack下标*/
ch = ex[t];
t++;
while (ch !='')
{
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
{
printf("\n\t除零错误!\n");
exit(0); /*异常退出*/
}
top--;
break;
default:
d = 0;
while (ch >= '0' && ch <= '9')
{
d = 10 * d + ch - '0'; /*将数字字符转化为对应的数值*/
ch = ex[t];
t++;
}
top++;
stack[top] = d;
}
ch = ex[t];
t++;
}
printf("\n\t计算结果:%g\n", stack[top]);
}
intmain()
{
trans();
compvalue();
system("pause");
return 0;
}
数据结构版
int precede(char op){
int x;
switch(op){
case '*': x=2; break;
case '/': x=2; break;
case '+': x=1; break;
case '-': x=1; break;
default : x=0;
}
return x;
}
char *RPExpression(char *e){
/* 返回表达式e的逆波兰式 */
char *c;
c=(char*)malloc(sizeof(char)*20);
//不能用char c[]Stack s1;InitStack(s1);
int i=0,j=0;
char ch;
Push(s1,'@');
ch=e[i++];
while(ch!= 0){
if(ch=='('){
Push(s1,ch);
ch=e[i++];
}
else
if(ch==')'){
while(Top(s1)!='('){
Pop(s1,c[j++]);
}
/* to[j++]=pop(&s1);*/
Pop(s1,ch);
ch=e[i++];
}else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){
char w;
w=Top(s1);
while(precede(w)>=precede(ch)){
Pop(s1,c[j++]);
w=Top(s1);
}
Push(s1,ch);
ch=e[i++];
}else{
//while((ch='a')||(ch='A')){c[j++]=ch;ch=e[i++];
//}
//c[j++]=' ';}
}
Pop(s1,ch);
while(ch!='@'){
c[j++]=ch;
Pop(s1,ch);
}
//c[j++]=;c[j++]=0;
return c;
}
还有一种方法,用二叉树。
