#include<stdbool.h>
#include<stdlib.h>
#defineSTACK_SIZE 20
intmake_empty(void)
boolis_empty(void)
boolis_full(void)
voidpush(char )
voidpop(char )
voidstack_overflow(void)
voidstack_underflow(void)
charcontents[STACK_SIZE]= {0},top
intmain(int argc, char *argv[])
{
char ch='1'
while(ch!='q'){
make_empty()
printf("Enter an RPNexpression:")
do{
scanf(" %c",&ch)
if(ch>='1'&&ch<='9')
push(ch)
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){
top--pop(ch)
}
else if(ch=='='){
if((top-1)==0)
pop(ch)
else
printf("Nunber notused!")
break
}
else if(ch=='\n')
else{
ch='q'break /*其它情况置为退出标志q*/
}
}
while(ch!='\n')
}
return 0
}
intmake_empty(void){
/* return top=0
}
boolis_empty(void){
return top==0
}
boolis_full(void){
return top==STACK_SIZE
}
voidpush(char ch){
if(is_full())
stack_overflow()
else
contents[top++]=ch-'0'
}
voidpop(char ch){
if(is_empty())
stack_underflow()
else
switch(ch){
case'+':contents[top-1]+=contents[top]break
case '-':contents[top-1]-=contents[top]break
case'*':contents[top-1]*=contents[top]break
case'/':contents[top-1]/=contents[top]break
case '=':printf("Value ofexpression:%d\n",(int)contents[0])break
}
}
voidstack_overflow(void){
printf("Expression is toocomplex!")
exit(EXIT_FAILURE)
}
voidstack_underflow(void){
printf("Not enough operands inexpression!")
exit(EXIT_FAILURE)
}
逆波兰式子又叫做后缀表达式。（相对于前缀和中缀，但是它俩都破坏了式子本身，所以用后缀）
12+3应该表达为12 3+。（实际无空格，为了好看）
先解决一个问题，就是123+会不会认为是1和23或者1和2和3，其实是不会的。一般后缀式都是用栈存储的，你在定义栈的时候里面的elemtype e（当然也可以用别的就是举例），这个elemtype是重命名的int。scanf或者cin输入的时候，你先输入12，这个就被存在栈的第一空里面（因为是%d嘛），再输入3就被存在第二空里面了。这个不会混淆。
逆波兰算法是这么工作的：在后缀式中扫描，可能会扫描到一堆数字，但是这时候如果扫描到了一个运算符（加减乘除等），这时候提取运算符并提取运算符前面紧挨着的那两个数字（注意是紧挨），然后这两个数字和这一个运算符进行运算。比如123+，扫描得12，扫描得3，扫描得+（电脑得到了+这个运算符），紧接着取前面紧挨的12和3,进行运算，就是12+3了。如(2+1) * 3就是21+3*。扫描得2，扫描得1，扫描得+，ok这时候2+1=3,3入栈，重新while扫描。扫描得3（刚才算出来刚入栈的那个），扫描得3，扫描得*，ok这时候3*3=9。
1+23这种后缀式是表达不出来的。后缀它的意义就在于两个数，他们的运算符关系紧挨在他们后面。这个1+只有一个数，还原算是就是+1，无意义。
