逆波兰式也叫后缀表达式，这里先简单帮大家理解一下概念性问题。
像我们平常使用到的表达式如
(
a
+
b
)
∗
c
、
2
+
5
∗
3
(a+b)*c、2+5*3
(a+b)∗c、2+5∗3等都是中缀表达式，对我们来说是最能理解的，但是计算机则理解起来比较困难，而其相应的后缀表达式为
a
b
+
c
∗
、
253
∗
+
ab+c*、253*+
ab+c∗、253∗+则更好的便于计算机的理解和处理。最直观的是用树来给大家展示：
（以
(
a
+
b
)
∗
c
(a+b)*c
(a+b)∗c为例）
通过图片发现，对树进行中序遍历得到的就是中缀表达式；对树进行后序遍历得到的就是后缀表达式，这也就是其名字的由来。想必大家一定恍然大悟了吧（嘻嘻）。
首先需要一个初始字符串、输出字符串和一个栈
对初始字符串的每一个字符进行如下处理：
在计算过逆波兰式的基础上来求解表达式的值，计算表达式的结果。
对逆波兰式操作后获得的字符串的每个字符进行如下处理：
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//定义栈
typedef struct{
char data[100];
int top;
int bottom;
}stack;
//定义全局变量
char str[10];
int n=0;
//创建栈
stack *StackCreate(){
stack *p=(stack*)malloc(sizeof(stack));//分配新空间
if(p==NULL)//分配失败
return 0;
p->bottom=p->top=0;//分配成功
return p;
}
//入栈
void StackInput(stack *p,char str){
p->data[p->top]=str;//存入栈中
p->top++;//栈顶指针加1
//printf("%c",p->data[p->top-1]);
}
//出栈
char StackOutput(stack *p,char sp){
if(p->top!=p->bottom){//栈非空
sp=p->data[p->top-1];//栈顶内容输出
p->top--;//栈顶减1
//printf("%c",str);
return sp;
}
}
//优先级比较
int prior(char a){
if(a=='+'|a=='-')
return 1;
else if(a=='*'|a=='/')
return 2;
else
return 0;
}
//逆波兰式
void rpn(char *s,stack *p){
int i,j;
char sp;
if(s[0]=='-'){//若第一个数为负数，则在其前面加一个0
for(i=0;i<strlen(s);i++)
s[strlen(s)-i]=s[strlen(s)-i-1];
s[0]='0';
}
for(i=0;i<strlen(s);i++){
if(s[i]>='0'&&s[i]<='9'){//s[i]是操作数
str[n++]=s[i];
}
if(s[i]=='('){//s[i]是左括号
StackInput(p,s[i]);
}
if(s[i]==')'){//s[i]是右括号
while(p->data[p->top-1]!='('){
str[n++]=p->data[p->top-1];
p->top--;
}
p->top--;
}
while(s[i]=='+'|s[i]=='-'|s[i]=='*'|s[i]=='/'){//s[i]是运算符
if(p->bottom==p->top|p->data[p->top-1]=='('|prior(s[i])>prior(p->data[p->top-1])){//若栈是空 或 栈顶为( 或 s[i]优先级高于栈顶元素,则入栈
StackInput(p,s[i]);
break;
}
else//反之栈顶元素出栈，继续while循环
str[n++]=StackOutput(p,sp);
}
}
while(p->bottom!=p->top){//若栈未空，将剩余的字符输出
str[n++]=p->data[p->top-1];
p->top--;
}
}
//计算表达式的值
void result(stack *p,char *str){
int i,j=0;
char sp,m,n;
for(i=0;i<strlen(str);i++){
if(str[i]>='0'&&str[i]<='9')//若为操作数，直接压入战中
StackInput(p,str[i]);
while(str[i]=='+'|str[i]=='-'|str[i]=='*'|str[i]=='/'){//若为运算符，从栈中取出两个进行运算，将结果再存入栈中
m=p->data[p->top-1];//栈顶
n=p->data[p->top-2];//栈顶下一个
p->top=p->top-2;
if(str[i]=='+')
j=((int)n-48)+((int)m-48);
if(str[i]=='-')
j=((int)n-48)-((int)m-48);
if(str[i]=='*')
j=((int)n-48)*((int)m-48);
if(str[i]=='/')
j=((int)n-48)/((int)m-48);
StackInput(p,(char)(j+48));//将结果再存入栈中
break;
}
}
printf("\n表达式的值为：\n%d",(int)p->data[p->top-1]-48);//读出最后的值
}
//主函数
int main(){
int i,j;
int r;
stack *p;//定义栈名
p=StackCreate();//创建栈
char s[10];
printf("输入中缀表达式：\n");
scanf("%s",s);
rpn(s,p);//调用逆波兰式
printf("逆波兰式为：\n");
for(i=0;i<n;i++)//输出逆波兰式
printf("%c",str[i]);
result(p,str);//进行求解表达式的值
}
//大家注入输入表达式的时候，括号千万要区分中英文，谨记
代码注释的很清楚明了，希望大家能够真正明白理解，若有何疑问请留下评论，第一时间看到就会回复。
