中缀表达式：

把运算符放在参与运算的两个操作数中间的表达式称作中缀表达式例：“3+4*5-6/2”，因为中缀表达式计算时必须按照优先级从左向右计算，所以计算机在进行中缀表达式求值时比较麻烦，而后缀表达式求值比较方便。

后缀表达式：

把运算符放在参与运算的两个操作数后面的表达式称作后缀表达式。

例：中缀表达式：3+4*5-6/2

转换成后缀表达式： 3 4 5 * + 6 2 / -

中缀表达式：9-8*（4-3）

转换成后缀表达式： 9 8 4 3 - * -

转换规则：

按照优先级，把每个运算符都移到它的两个操作数的后面，再删除所有的括号

后缀表达式的求值：

从左向右一次扫描后缀表达式，遇到运算符将将它前面的两个运算数取出并计算，并将结果带入后缀表达式，直到扫描到最后一个后缀表达式。

表达式求值：

表达式求值是栈应用的一个基本例子，输入一个中缀表达式，求取相应的结果。因为计算机不会算中缀表达式，所以我们先要将中缀表达式转换成相应的后缀表达式再进行计算。要转成相应的后缀表达式，我们应该创建两个栈，一个用来存放操作数，一个用来存放运算符。

中缀表达式求值的算法：

从左向右扫描中缀表达式，若遇到操作数，则直接压入运算数栈，若遇到符号，则与运算符栈的栈顶元素比较，若读取符号的优先级高，则读取的符号进栈；否则让运算符栈的栈顶符号退栈并且将运算数栈最上面的两个元素退栈，然后将运算的结果压入运算数栈，一直这样循环直到读取的符号的优先级高于运算符栈顶元素。

因为每读取一个符号就要与运算符栈的栈顶元素进行优先级比较，我们不能每次都写一大堆if else语句，所以我们可以将运算符的优先级的结果放到一个二维数组中，然后利用查表法，判断优先级。

因为当我们读取第一个符号时，运算符栈还是个空栈，为了方便比较，我们在栈底压入一个#，并规定#的优先级最低，并将“#”作为表达式输入结束的标志。

为了方便索引：我们再创建一个一维数组，

char arr[7] = { '+' , '-', '*', '/', '(', ')', '#' };通过它来找到栈顶符号和读取符号在优先级数组中的位置。

实现：输入一个合法的中缀表达式，只包含“+-*/”四种运算符，并以“#”作为结束标志。//函数声明：#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_MEMORY20//初始时开辟栈的内存大小#defineSTACK_GROW_MEMORY10//当栈满时，追加内存的大小constchararr[7];//声明一个存放运算符的一维数组，作为索引voidinit_priority_list(charlist[][7]);//初始化符号表typedefstructstack_num//声明一个存放运算数的结构体类型{int*esp;//栈顶指针int*ebp;//栈底指针intsize;//记录当前栈空间最多能存几个元素}stack_num;voidcreatstack_num(stack_num*S);//创建存放运算数的栈voidpush_num(stack_num*S,intx);//将参数x中的数压入运算数栈中intpop_num(stack_num*S,int*x);//弹出栈顶元素，并通过形参x带回typedefstructstackpop_opreation//声明一个存放运算符的结构体类型{char*esp;//栈顶指针char*ebp;//栈底指针intsize;//记录当前栈空间最多能存几个元素}stack_operation;voidcreatstack_operation(stack_operation*S);//创建一个存放运算符的栈voidpush_operation(stack_operation*S,charsymbol);//将符号压入运算符栈中intpop_opreation(stack_operation*S,char*top);//将运算符栈中的栈顶元素弹出//函数实现：charjudge_priority(stack_operation*S,charc);//判断读取的运算符与栈顶符号的优先级,并返回intoperation(inta,charsymbol,intb);//对运算数进行相的运算，并将结果返回intjudge_num(charc);//判断读取的是符号还是数字，如果是数字返回1#include"expression.h"constchararr[7]={'+','-','*','/','(',')','#'};//通过arr[7]来查找list[][]中的优先级voidinit_priority_list(charlist[][7])//初始化优先级列表{intarr2[7]={1,1,2,2,3,0,-1};//列作为栈顶元素，行代表读取的运算符for(inti=0;i<7;i++){for(intj=0;j<7;j++){if((i==4&&j==5)||(i==6&&j==6)//令'('与‘）’，‘#’与‘#’优先级相同list[i][j]='=';else{if(arr2[i]>=arr2[j])list[i][j]='>';//栈顶优先级高elseif(arr2[i]<=arr2[j])list[i][j]='<';//读取的运算符优先级高}}}}voidcreatstack_num(stack_num*S)//创建运算数栈{S->ebp=(int*)malloc(sizeof(int)*STACK_INIT_MEMORY);if(S->ebp==NULL)//判断动态内存是否开辟成功exit(1);S->size=STACK_INIT_MEMORY;S->esp=S->ebp;//让栈顶指针指向栈底}voidpush_num(stack_num*S,intx){if(S->esp-S->ebp>=S->size)//判断当前栈是否已满{//栈满追加空间S->ebp=(int*)realloc(S->ebp,sizeof(int)*(S->size+STACK_GROW_MEMORY));if(S->ebp==NULL)exit(1);S->esp=S->ebp+S->size;//让栈顶指针向后偏移指向要入栈的位置S->size+=STACK_GROW_MEMORY;//更新栈的size}*S->esp++=x;}intpop_num(stack_num*S,int*x){if(S->esp==S->ebp)return0;//如果是空栈，则返回0else{*x=*--S->esp;return1;//如果弹出成功，返回1，并将弹出的元素保存在x中带回}}voidcreatstack_operation(stack_operation*S)//创建运算符栈{S->ebp=(char*)malloc(sizeof(char)*STACK_INIT_MEMORY);if(S->ebp==NULL)exit(1);//判断动态内存是否开辟成功S->size=STACK_INIT_MEMORY;S->esp=S->ebp;}voidpush_operation(stack_operation*S,charsymbol){if(S->esp-S->ebp>=S->size)//如果栈满则追加空间{S->ebp=(char*)realloc(S->ebp,sizeof(char)*(S->size+=STACK_GROW_MEMORY));if(S->ebp==NULL)exit(1);S->ebp=S->ebp+S->size-STACK_GROW_MEMORY;}*S->esp++=symbol;}intpop_opreation(stack_operation*S,char*top){if(S->esp==S->ebp)return0;//如果栈是空栈，则返回0else*top=*--S->esp;//否则将弹出的匀速保存在top中带回return1;}charjudge_priority(stack_operation*S,charc)//判断栈顶运算符与读取的运算符的优先级{charlist[7][7];init_priority_list(list);//初始化优先级表intline=0;introw=0;for(line=0;line<7;line++){if(arr[line]==*(S->esp-1))//将栈顶符号在arr[]中的位置作为行下标break;}for(row=0;row<7;row++){if(arr[row]==c)//将读取的运算符在arr[]中的位置作为列下标break;}returnlist[line][row];//通过优先级表，返回优先级关系}intoperation(inta,charsymbol,intb){intret=0;switch(symbol){case'+':ret=a+b;break;case'-':ret=a-b;break;case'*':ret=a*b;break;case'/':ret=a/b;break;default:break;}returnret;}intjudge_num(charc)//判断读取的是不是数字{inti=0;for(i=0;i<7;i++){if(arr[i]==c)break;}if(i==7)return1;//如果是数字则返回1elsereturn0;//如果不是数字则返回0}#include"expression.h"intmain(){stack_numnum_stack;creatstack_num(&num_stack);//建立一个运算数栈stack_operationoperator_stack;creatstack_operation(&operator_stack);//建立一个运算符栈intc;charsymbol;inta=0;intb=0;intret=0;push_operation(&operator_stack,'#');//将‘#’入栈，作为运算符栈的栈底c=getchar();while(c!='#'||*(operator_stack.esp-1)!='#'）//接受表达式并且判断表达式是否输入完毕{if(judge_num(c))//如果是数字则进入运算数栈{intnum=0;while(judge_num(c))//把连续的char类型的数字全部读取并转化成相应的整数{num=num*10+(c-'0');//因为这是的运算数是char类型，所以先要转换成intc=getchar();}push_num(&num_stack,num);//将运算数入栈}else{switch(judge_priority(&operator_stack,c))//判断读取的运算符与栈顶符号的优先级关系{case'<'://如果读取的符号优先级高，则直接进入运算符栈push_operation(&operator_stack,c);c=getchar();break;case'>'://如果读取的符号优先级低，则栈顶符号退栈，将运算结果入栈pop_opreation(&operator_stack,&symbol);//则栈顶符号退栈pop_num(&num_stack,&b);pop_num(&num_stack,&a)//将运算数栈栈顶的两个元素弹出ret=operation(a,symbol,b);//将这两个元素进行运算push_num(&num_stack,ret);//将运算结果入栈break;case'='://当读取到“）”时则一直退栈直到遇到“（”pop_opreation(&operator_stack,&symbol);c=getchar();break;default:break;}}}printf("%d\n",*(num_stack.esp-1));//将运算数栈最后剩下的数输出system("pause");free(num_stack.ebp);free(operator_stack.ebp);return0;}