c语言中缀后缀算术表达式求值用栈实现

⽤栈对后缀表达式求值的算法（五种）转载出处：第⼀种/* 此程序的功能是求出⽤户输⼊的整形表达式的值*//*输⼊的表达式请⽤#结尾，⽐如：2+3+5，应输⼊：2+3+5#。

*/#include <stdio.h>#define MAXSIZE 16typedef struct{int data[MAXSIZE];int top;int base;}seqstack; /* 顺序栈的定义*//*以下为函数声明*/void InitStack(seqstack *);int Empty(seqstack *);void Push(seqstack *, int );int Pop(seqstack *);int GetTop(seqstack *);int Operate(int ,char ,int );char Proceed(char ,char );int In(char );int EvalExpres(void);/* 定义两个栈分别存放运算符和操作数*/seqstack StackR,StackD;/*主函数*/int main(){int v;char ch;while(1){printf("end with #,for example 2+3+5 input:2+3+5#\n");printf("calculate:") ;v = EvalExpres();printf("The result is:%d",v);/*以下为程序控制*/printf("\nInput 'q' to quit and ENTER run again:");do{scanf("%c",&ch);if(ch == 'q' || ch == 'Q')exit(0);}while(ch!='\n');system("cls");}return 0;}void InitStack(seqstack *s){ s->top = 0;s->base = 0;} /* 初始化栈*/int Empty(seqstack *s){ if(s->top == s->base)return 1;elsereturn 0;} /* 判断栈是否为空*/void Push(seqstack *s, int x){if(s->top == MAXSIZE){ printf("OVER FLOW!\n");exit(0);}else{ s->data[s->top] = x;s->top++;}} /* 进栈 */int Pop(seqstack *s){ int e;if(Empty(s)){ printf("Under flow!\n");return 0;} /* 下溢*/else{ s->top--;e = s->data[s->top];return e;}} /* 出栈*/int GetTop(seqstack *s) /*取栈顶元素*/{if(Empty(s)){ printf("Under flow!\n");return 0;}elsereturn s->data[s->top-1];}int EvalExpres(void) /* 表达式求解函数*/{int a,b,i=0,s=0;char c[80],r;InitStack(&StackR);Push(&StackR,'#');InitStack(&StackD);printf(" end with #");gets(c);while(c[i]!='#' || GetTop(&StackR)!='#'){if(!In(c[i])) /* 判断读⼊的字符不是运算符是则进栈*/{ if(c[i] >= '0' && c[i] <= '9'){s += c[i]-'0';while(!In(c[++i])) /*此处实现的功能为当输⼊的数字为多位数时*/{ s*=10;s += c[i]-'0';}Push(&StackD,s+'0');s = 0;}else{printf("wrong!\n");return 0;}}elseswitch(Proceed(GetTop(&StackR),c[i])) /* 此函数⽤来⽐较读取的运算符和栈顶运算符的优先级*/ {case '<': /* 栈顶的元素优先级⾼*/i++;break;case '=': /* 遇到匹配的⼩括号时则去掉他*/Pop(&StackR);i++;break;case '>': /* 栈顶的优先级低则出栈并将结果写⼊栈内*/r = Pop(&StackR);a = Pop(&StackD)-'0';b = Pop(&StackD)-'0';Push(&StackD,Operate(a,r,b)) ;break;}}return (GetTop(&StackD)-'0'); /* 返回运算结果*/}int In(char c) /*问题2：解决In函数问题:判断C是否为运算符是返回1否则返回0*/{char ch[7]={'+','-','*','/','#','(',')'};int i;for(i = 0; i < 7; i++)if(c == ch[i])return 1;return 0;}char Proceed(char op,char c) /*op为栈顶元素，c为当前读⼊的运算符,⽐较⼆者的优先级*/ { /*问题1：解决Proceed函数*/char ch;if(op=='(' && c==')' || op=='#' && c=='#' )ch = '=';elseif(op=='+' || op=='-') /*栈顶元素为‘+’或‘-’的时候*/switch(c){case '+':case '-':case ')':case '#': ch = '>'; break;case '*':case '/':case '(': ch = '<';}elseif(op=='*' || op=='/') /*栈顶元素为‘*’或‘/’的时候*/switch(c){case '+':case '-':case '*':case '/':case ')':case '#': ch = '>'; break;case '(': ch = '<';}elseif(op=='(') /*栈顶元素为‘(’的时候*/switch(c){case '+':case '-':case '*':case '/':case '#': printf("Error!\n"); exit(0);}elseif(op==')') /*栈顶元素为‘)’的时候*/switch(c){case '+':case '-':case '*':case '/':case '#': ch = '>'; break;case '(': printf("Error!\n"); exit(0);}elseif(op=='#') /*栈顶元素为‘#’的时候*/ switch(c){case '+':case '-':case '*':case '/':case '(': ch = '<'; break;case ')': printf("Error!\n"); exit(0);}return ch;}/* 问题3：解决Operate函数*/int Operate(int a,char r,int b) /*返回由aRb的值 */ {int s;int d1 = a;int d2 = b; /*把字符ab变为对应数字*/switch(r){case '+': s = d1+d2; break;case '-': s = d2-d1; break;case '*': s = d1*d2; break;case '/': s = d2/d1;}return (s+'0');}第⼆种#include <stdio.h>#include <malloc.h>#define MaxSize 50void trans(char *exp,char *postexp){struct{char data[MaxSize];int top;} op;int i=0;op.top=-1;while(*exp!='\0'){switch(*exp){case '(':op.top++;op.data[op.top]=*exp;exp++;break;case ')':postexp[i++]=op.data[op.top];op.top--;}op.top--;exp++;break;case '+':case '-':while(op.top!=-1&&op.data[op.top]!='('){postexp[i++]=op.data[op.top];op.top--;}op.top++;op.data[op.top]=*exp;exp++;break; case '*':case '/':while(op.data[op.top]=='*'||op.data[op.top]=='/') {postexp[i++]=op.data[op.top];op.top--;}op.top++;op.data[op.top]=*exp;exp++;break; case ' ':break;default:while(*exp>='0'&&*exp<='9'){postexp[i++]=*exp;exp++;}postexp[i++]='#';}}while(op.top!=-1){postexp[i++]=op.data[op.top];op.top--;}postexp[i]='\0';}float compvalue(char *postexp){struct{float data[MaxSize];int top;} st;float a,b,c,d;st.top=-1;while(*postexp!='\0'){switch(*postexp){case '+':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b+a;st.top++;st.data[st.top]=c;break;case '-':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b-a;break;case '*':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b*a;st.top++;st.data[st.top]=c;break;case '/':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;if(a!=0){c=b/a;st.top++;st.data[st.top]=c;}else{printf("\n\t除零错误!\n");exit(0);}break;default:d=0;while(*postexp>='0'&&*postexp<='9'){d=10*d+*postexp-'0';postexp++;}st.top++;st.data[st.top]=d;break;}postexp++;}return st.data[st.top];}int main(){char exp[MaxSize],postexp[MaxSize];while(scanf("%s",&exp)!=EOF){trans(exp,postexp);printf("zhongzhuibiaodashi: %s\n",exp);printf("houzuibiaodashi: %s\n",postexp);printf("zhi: %g\n",compvalue(postexp)); }return 0;}第三种#include<stdio.h>#include<stdlib.h>#define add 43#define subs 45#define mult 42#define div 47#define MAXSIZE 100int data[MAXSIZE];int top;}seqstack;seqstack *s;seqstack *Init() /*栈的初始化*/{seqstack *s;s=(seqstack *)malloc(sizeof(seqstack)); if(!s){printf("FULL!");return NULL;}else{s->top=-1;return s;}}int Empty(seqstack *s) /*栈空的判断*/{if(s->top==-1) return 1;else return 0;}int Push(seqstack *s,int x) /*⼊栈*/{if(s->top==MAXSIZE-1) return 0;else{s->top++;s->data[s->top]=x;return 1;}}int Pop(seqstack *s,int *x) /*出栈的算法*/ {if (Empty(s)) return 0;else{*x=s->data[s->top];s->top--;return 1;}}int Top(seqstack *s) /*取栈顶元素*/ {if(Empty(s)) return 0;else return s->data[s->top];}int eval(char t,int a1,int a2){switch(t){case add:return(a1+a2);case subs:return(a1-a2);case mult:return(a1*a2);case div:return(a1/a2);}}void main(){char c;int op1,op2,temp,c1;s=Init();printf("Input:(end with #)\n");while((c=getchar())!='#'){if(c=='')continue;if(c>47&&c<58){putchar(c);c1=c-48;}else if(c==add||c==subs||c==mult||c==div){putchar(c);Pop(s,&op1);Pop(s,&op2);temp=eval(c,op2,op1);Push(s,temp);}else printf("It's wrong!\n");}Pop(s,&op1);printf("=%d\n",op1);getch();}第四种#include<stdio.h>#include<stdlib.h>#define add 43#define subs 45#define mult 42#define div 47#define MAXSIZE 100typedef struct{int data[MAXSIZE];int top;}STKzone;typedef STKzone *STK;typedef enum{ture=1,false=0} bool;typedef enum{ok,error} status;STKzone expSTKzone;STK expSTK;STK initSTK(STKzone *stkzone) /*栈的初始化*/{STK p;p=stkzone;p->top=0;}status push(int *term,STK pstk) /*⼊栈*//*term前可以没有*，同时将第28、71、81⾏稍作修改即可 */ {if(pstk->top==MAXSIZE) return error;pstk->data[pstk->top]=*term;pstk->top++;return ok;}bool emptySTK(STK pstk) /*栈空的判断*/{return (pstk->top==0);}status pop(int *pdata,STK pstk) /*出栈的算法*/{if (emptySTK(pstk)) return error;(pstk->top)--;*pdata=pstk->data[pstk->top];return ok;}void synerror(){printf("\nyu fa cuo wu!");}{switch(tag){case add:return(a1+a2);case subs:return(a1-a2);case mult:return(a1*a2);case div:return(a1/a2);}}main(){ char c;int op1,op2,temp,c1;expSTK=initSTK(&expSTKzone);printf("Input:\n");while((c=getchar())!='\n'){if(c=='')continue;if(c>47&&c<58){putchar(c);c1=c-48;if(push(&c1,expSTK)==error){printf("\n too long!\n");}}else if(c==add||c==subs||c==mult||c==div) {putchar(c);if(pop(&op1,expSTK)==error)synerror(); if(pop(&op2,expSTK)==error)synerror(); temp=eval(c,op2,op1);push(&temp,expSTK);}else synerror();}if(pop(&op1,expSTK)==error) synerror();if(!(emptySTK(expSTK))) synerror();printf("=%d\n",op1);getch();}第五种#include<stdio.h>#include<stdlib.h>#define add 43#define subs 45#define mult 42#define div 47#define MAXSIZE 100typedef struct{int stkdata[MAXSIZE];int top;}stack;int init_stack(stack *s){ s=(stack *)malloc(sizeof(stack));if(!s){printf("FULL!\n");return 0;}else{s->top=-1;return 1;}}int push(stack *s,int x){ printf("over flow\n");return 0;}else{s->top++;s->stkdata[s->top]=x;return 1;}}char pop(stack *s){ char e;if(s->top==-1){printf("under flow \n");return 0;}e=s->stkdata[(s->top)--];return e;}void main(){stack *s1;int length,i,num1,num2,result,sum;char s[100];init_stack(s1);printf("please input \n");printf("warning:must less than 100\n");gets(s);length=strlen(s);for(i=0;i<=length-1;i++){ if(s[i]>='1'&&s[i]<='9')push(s1,s[i]-48);else{ num1=pop(s1);num2=pop(s1);switch(s[i]){case add: {sum=num1+num2;push(s1,sum);break;}case subs:{sum=num2-num1;push(s1,sum);break;}case div:{sum=num2/num1;push(s1,sum);break;}case mult:{sum=num1*num2;push(s1,sum);break;}}}}result=s1->stkdata[s1->top];printf("result is %d\n",result);getch();}在研究表达式。

一、设计思想计算算术表达式可以用两种方法实现:1.中缀转后缀算法此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算.具体实现方法如下:（1）中缀转后缀需要建一个操作符栈op和一个字符数组exp,op栈存放操作符，字符数组用来存放转换以后的后缀表达式。

首先，得到用户输入的中缀表达式,将其存入str数组中。

对str数组逐个扫描，如果是数字或小数点,则直接存入exp数组中，当扫描完数值后,在后面加一个＃作为分隔符。

如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组,直到遇到左括号，左括号丢掉。

然后继续扫描下一个字符,直到遇到str中的结束符号\0，扫描结束。

结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空.到此在exp数组最后加结束字符\0。

我们就得到了后缀表达式。

（2）后缀表达式计算此时需要一个数值栈od来存放数值。

对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。

当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。

继续扫描,知道扫描结束,此时值栈中的数值就是计算的结果,取出返回计算结果。

2。

两个栈实现算法此算法需要两个栈，一个值栈od，一个操作符栈op。

将用户输入的数学表达式存入str数组中,对其数组进行逐个扫描。

当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中,一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。

如果遇到操作符，若op栈为空，直接入栈;若栈不为空，与栈顶元素比较优先等级,若比栈顶操作符优先等级高，直接入op栈,如果低于或等于栈顶优先等级，op栈出栈,再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op 栈。

算法笔记--中缀表达式转后缀表达式后缀表达式计算中缀表达式转后缀表达式规则中缀表达式a + b*c + (d * e + f) * g，转换成后缀表达式则为a b c * + d e * f + g * +转换过程需要⽤到栈，具体过程如下：1 如果遇到操作数，我们就直接将其输出。

2 如果遇到操作符，则我们将其放⼊到栈中，遇到左括号时我们也将其放⼊栈中。

3 如果遇到⼀个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为⽌。

注意，左括号只弹出并不输出。

4 如果遇到任何其他的操作符，如+, *, (等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为⽌。

弹出完这些元素后，才将遇到的操作符压⼊到栈中。

有⼀点需要注意，只有在遇到 )的情况下我们才弹出( ，其他情况我们都不会弹出( 。

即：若操作符op的优先级⾼于栈顶操作符的优先级，则压⼊操作符栈若操作符op的优先级⼩于等于栈顶操作符的优先级，则将操作栈的操作符不断弹出到后缀表达式中，直到op的优先级⾼于栈顶操作符的优先级5 如果我们读到了输⼊的末尾，则将栈中所有元素依次弹出。

实例a +b *c + (d *e + f) * g1. ⾸先读到a，直接输出。

2. 读到“+”，将其放⼊到栈中。

3. 读到b，直接输出。

此时栈和输出的情况如下：4. 读到“*”，因为栈顶元素"+"优先级⽐" * " 低，所以将" * "直接压⼊栈中。

5. 读到c，直接输出。

此时栈和输出情况如下：6. 读到" + "，因为栈顶元素" * "的优先级⽐它⾼，所以弹出" * "并输出，同理，栈中下⼀个元素" + "优先级与读到的操作符" + "⼀样，所以也要弹出并输出。

然后再将读到的" + "压⼊栈中。

一、设计思想第一种算法：将中缀表达式转为后缀表达式，然后通过后缀表达式计算出算术表达式的结果。

核心思想：第一步：中缀变后缀。

首先，我们做出一个统一的Node结构体，结构体内部包含四个属性，分别是操作符的字符‘op’，char类型；操作符的优先级‘level’，int 类型；数字的浮点数数值‘od’，float类型；Node的标识符，int类型。

然后，定义一个Node结构体类型的数组*listNode，这里的*listNode用的是全局变量，为了方便在得到后缀表达式后，不需再传递给计算的方法。

定义一个存放操作符的栈，遍历用户输入的算术表达式（不考虑错误情况），在遍历的过程中如果遇到数字，直接将数字存放在*listNode里面；如果遇到了操作符，则判断操作符栈目前是不是为空，如果为空，直接将遇到的操作符放入操作符栈中，如果操作符栈不为空，那么观察操作符栈中栈顶的操作符，然后再次判断当前遇到的操作符的优先级是不是比栈顶的操作符的优先级高，如果是，那么将当前的操作符入操作符栈；如果不是，那么将操作符栈的栈顶操作符取出，追加到*listNode中，然后继续观察栈顶操作符，直到当前的操作符的优先级比栈顶操作符的优先级高或者操作符栈为空时，将当前操作符入操作符栈。

如果遇到了左括号，那么定义其优先级为最低，然后直接将左括号入操作符栈。

如果遇到了右括号，那么开始从操作符栈中取出操作符追加到*listNode中，直到遇到了与之对应的左括号，然后将左括号和右括号一起销毁。

当遍历完成了算术表达式之后，这时判断操作符栈是否为空，如果不为空，那么从操作符栈中依次取出栈顶操作符追加到*listNode中，直到操作符栈为空，那么就代表我们将中缀表达式转变成为了后缀表达式。

第二步：通过得到的后缀表达式，计算算术表达式。

首先，定义一个数字栈用来存放数值。

然后，遍历*listNode中的每一个Node，如果Node是一个数字，那么就将数字入数字栈，如果Node是一个操作符，那么就从数字栈中依次取出栈顶的两个数字，然后根据操作符计算这两个数字，将得到的结果再次入数字栈，直到遍历*listNode完成，最终数字栈中会只剩下一个Node，那就是我们计算出算术表达式的结果，将结果返回给main 函数用来输出。

数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：网络工程班级：网络1班指导教师：吴亚峰姓名：王嘉宇学号：201214620111目录一、设计思想 (01)二、算法流程图 (01)三、源代码 (04)四、运行结果 (12)五、遇到的问题及解决 (13)六、心得体会 (14)一、设计思想（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。

第一遍扫描中缀表达式，需要一个运算符栈和一个数组。

运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。

首先将中缀表达式挨个扫描。

如果是数字，则直接放在后缀表达式数组中，依次存放。

如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直接入栈。

栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。

如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。

如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，直到遇到左括号为止，此时将左括号从栈顶删除。

按此方法，直到后缀表达式转换成功。

第二遍扫描后缀表达式，此时需要一个数栈。

扫描时如果遇到数字，则直接放到数栈中。

如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进行运算符运算。

将运算的结果放入栈中。

之后接着扫描后缀表达式。

另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。

当栈中只有一个数字时，这个数字就是我们要求的表达式的值。

（2）直接计算表达式的值。

这种方法需要两个栈，一个运算符栈，一个数栈。

只需扫描一遍中缀表达式，边运算边入栈。

当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。

c语言基于二叉树的表达式求值算法C语言中，基于二叉树的表达式求值算法主要包括两部分：中缀表达式转换为后缀表达式和后缀表达式求值。

1.中缀表达式转换为后缀表达式中缀表达式是我们常见的数学表达方式，例如3 + 4 * 2 - 5。

为了方便计算机求值，我们需要将中缀表达式转换为后缀表达式，也叫做逆波兰表达式。

转换的过程使用栈数据结构来实现。

具体算法如下：1.定义一个栈和一个结果字符串，栈用于存储操作符，结果字符串用于保存后缀表达式。

2.从左到右遍历中缀表达式的每一个字符。

3.如果当前字符是数字，直接将其加入结果字符串。

4.如果当前字符是左括号"("，将其入栈。

5.如果当前字符是右括号")"，则依次将栈顶的操作符弹出并加入结果字符串，直到遇到左括号为止，同时将左括号从栈中弹出。

6.如果当前字符是操作符，需要将栈中优先级比当前操作符高或者相等的操作符弹出并加入结果字符串，然后将当前操作符入栈。

7.遍历完所有字符后，将栈中剩余的操作符依次弹出并加入结果字符串。

8.最终结果字符串就是后缀表达式。

例如，对于中缀表达式3 + 4 * 2 - 5，转换为后缀表达式为3 4 2 * + 5 -2.后缀表达式求值后缀表达式求值算法使用栈数据结构来实现。

具体算法如下：1.定义一个栈，用于存储操作数。

2.从左到右遍历后缀表达式的每一个字符。

3.如果当前字符是数字，则将其转换为对应的整数并入栈。

4.如果当前字符是操作符，则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，根据操作符进行运算，得到结果后入栈。

5.遍历完所有字符后，栈顶的数字即为最终的结果。

例如，对于后缀表达式3 4 2 * + 5 -，求值的过程如下：1.入栈3。

2.入栈4。

3.入栈2。

4.弹出2和4，计算4 * 2 = 8，将8入栈。

5.弹出8和3，计算3 + 8 = 11，将11入栈。

6.入栈5。

7.弹出5和11，计算11 - 5 = 6，得到最终结果。

利用栈或二叉树将算术表达式输入串(只要求1位整数)转换为后缀式,然后计算该表达式利用栈或二叉树将算术表达式输入串(只要求1位整数)转换为后缀式,然后计算该表达式算术表达式的计算通常需要将中缀表达式转换为后缀表达式，然后使用栈或二叉树对后缀表达式进行计算。

首先，我们需要定义运算符的优先级。

在本例中，我们只考虑加法'+'和减法'-'两个运算符，其中加法的优先级较低。

接下来，我们可以使用栈来转换中缀表达式为后缀表达式。

具体步骤如下：1. 创建一个空栈和一个空字符串，用于存储后缀表达式。

2. 从左到右遍历中缀表达式的每个字符。

3. 对于每个字符，进行如下处理：- 如果是数字，则直接添加到后缀表达式字符串中。

- 如果是运算符，则比较其与栈顶运算符的优先级。

- 如果栈为空或栈顶运算符为'('，则直接将当前运算符入栈。

- 如果当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符入栈。

- 如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入后缀表达式字符串中，直到栈为空或栈顶运算符为'('，然后将当前运算符入栈。

- 如果是左括号'('，则直接将其入栈。

- 如果是右括号')'，则将栈顶运算符弹出并加入后缀表达式字符串中，直到遇到左括号'('，然后将左括号出栈但不加入后缀表达式字符串。

4. 遍历完中缀表达式后，将栈中剩余的运算符依次弹出并加入后缀表达式字符串中。

现在，我们已经将中缀表达式转换为后缀表达式。

接下来，我们可以使用栈或二叉树来计算后缀表达式。

1. 创建一个空栈，用于存储操作数。

2. 从左到右遍历后缀表达式的每个字符。

3. 对于每个字符，进行如下处理：- 如果是数字，则将其转换为整数并入栈。

- 如果是运算符，则从栈中弹出两个操作数，进行相应的运算，并将结果入栈。

4. 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。

栈是一种常见的数据结构，用于解决许多算法和数据处理问题。

在编程中，栈通常用于处理表达式求值问题。

本篇文章将介绍如何使用栈解决表达式求值问题，并给出对应的C语言代码。

1. 表达式求值问题介绍表达式求值是指计算一个数学表达式的值，通常涉及到四则运算、括号和优先级等概念。

给定一个表达式“3 + 4 * 2”，我们需要得到其计算结果为11。

在编程中，需要将该表达式转换为计算机可识别的形式，并使用算法进行求值。

2. 中缀表达式、前缀表达式和后缀表达式在计算机中常见的表达式有三种形式：中缀表达式、前缀表达式和后缀表达式。

其中，中缀表达式是通常人们在日常生活中使用的表达式形式，如“3 + 4 * 2”。

前缀表达式是运算符位于操作数之前的形式，例如“+ 3 * 4 2”。

后缀表达式则是运算符位于操作数之后的形式，例如“3 4 2 * +”。

3. 使用栈解决表达式求值问题在解决表达式求值问题时，我们可以利用栈的特性来简化计算过程。

具体步骤如下：3.1 将中缀表达式转换为后缀表达式我们需要将中缀表达式转换为后缀表达式，这样可以简化表达式的计算顺序。

具体转换规则如下：- 从左至右扫描中缀表达式的每个数字或符号。

- 如果是操作数，则直接输出。

- 如果是运算符，则弹出栈中所有优先级大于或等于该运算符的运算符，并将其压入栈中，然后压入该运算符。

- 如果是括号，则根据括号的不同情况进行处理。

通过以上规则，我们可以将中缀表达式转换为后缀表达式。

3.2 计算后缀表达式的值得到后缀表达式后，我们可以利用栈来计算其值。

具体步骤如下：- 从左至右扫描后缀表达式的每个数字或符号。

- 如果是操作数，则压入栈中。

- 如果是运算符，则弹出栈中的两个操作数进行相应的运算，并将结果压入栈中。

- 继续扫描直到表达式结束，栈中的值即为所求结果。

通过以上步骤，我们可以使用栈来解决表达式求值问题。

4. C语言代码实现以下是使用C语言实现栈来解决表达式求值问题的代码示例：```c#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct {int top;int capacity;int* array;} Stack;Stack* createStack(int capacity) {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->capacity = capacity;stack->top = -1;stack->array = (int*)malloc(stack->capacity * sizeof(int)); return stack;}int isFull(Stack* stack) {return stack->top == stack->capacity - 1; }int isEmpty(Stack* stack) {return stack->top == -1;}void push(Stack* stack, int item) {if (isFull(stack)) return;stack->array[++stack->top] = item;}int pop(Stack* stack) {if (isEmpty(stack)) return -1;return stack->array[stack->top--];}int evaluatePostfix(char* exp) {Stack* stack = createStack(strlen(exp)); for (int i = 0; exp[i]; i++) {if (isdigit(exp[i])) {push(stack, exp[i] - '0');} else {int val1 = pop(stack);int val2 = pop(stack);switch (exp[i]) {case '+':push(stack, val2 + val1); break;case '-':push(stack, val2 - val1); break;case '*':push(stack, val2 * val1); break;case '/':push(stack, val2 / val1); break;}}}return pop(stack);}int m本人n() {char exp[] = "34*2+";printf("The value of s is d\n", exp, evaluatePostfix(exp));return 0;}```以上代码实现了栈的基本功能，并利用栈来计算后缀表达式的值。

C语言实现中缀、后缀、前缀表达式相互转化并求值1.问题描述(1)表达式求值问题表达式是数据运算的基本形式。

人们的书写习惯是中缀式，如:11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。

表达式还有后缀式(如:22 7 4 - * 3 / 11 +)和前缀式(如:+ 11 / * 22 –7 4 3)。

后缀表达式和前缀表达式中没有括号，给计算带来方便。

如后缀式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。

2.数据结构设计(1)表达式求值问题由于表达式中有字符与数字两种类型，故定义结点一个标志域data，标志结点存储的为字符data=2还是数字data=1，再寻找结点中对应的存储位置，读取数字域data1,字符域data2。

而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。

typedef struct Node //定义存储中缀表达式的结点类型{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2 //定义存储前缀表达式的结点类型{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;3.运行、测试与分析(1)表达式求值问题(1)按提示输入中缀表达式，如图1.1所示。

如输入中缀表达式不正确，提示输入有误，如图1.2,1.3所示。

图1.1图1.2图1.3(2)选择表达式转换并求值方式。

按“1”选择中缀表达式求值，如图1.4所示。

图1.4(3)按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示。

图1.5(4)按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示。

原创作者：/p/hky_bd2010?from=zhidaousing System;using System.Collections.Generic;using System.Linq;using System.Text;namespace RPN{class Program{static void Main(string[] args){string infix = "2+3*4"; // 中缀string suffix = InfixChangeSuffix(infix); // 中缀转后缀double result=CalcSuffix(suffix.Split(',').ToArray());Console.WriteLine(result);}///<summary>///中缀转后缀///</summary>///<param name="infixExpression">中缀表达式</param>///<returns></returns>static string InfixChangeSuffix(string infixExpression){string suffix = string.Empty;string completeDigits = string.Empty;Stack<char> stack = new Stack<char>();for (int i = 0; i < infixExpression.Length; i++){if (IsOperator(infixExpression[i])) // 是否是运算符{if (!String.IsNullOrWhiteSpace(completeDigits)){suffix += completeDigits + ","; // 把前面的数字加入到后缀表达式里completeDigits = string.Empty; // 清空,待下次继续使用}if (stack.Count>0) // 如果栈里有元素，则判断当前符号与栈顶元素的优先级{char stackTopSymbol;if (infixExpression[i] == '(') // 如果是左括号则直接进栈{stack.Push(infixExpression[i]);}else if (infixExpression[i] == ')') // 如果是右括号,则出栈直到遇到左括号为止{stackTopSymbol = stack.Pop(); // 弹出栈顶元素do{if (stackTopSymbol != '(') suffix +=Convert.ToString(stackTopSymbol) + ",";if (stack.Count > 0) stackTopSymbol = stack.Pop();else break; // 中缀表达式有异常即四则运算不符合数学规则} while (stackTopSymbol != '('); // 直到遇到左括号为止则停止出栈}else{stackTopSymbol = stack.Peek(); // 拿栈顶元素出来,但不移除int curPriority = Priority(infixExpression[i]);int stackTop = Priority(stackTopSymbol);if (curPriority <= stackTop){do{suffix += stackTopSymbol + ",";stack.Pop(); // 栈顶元素优先级高当前符号,则弹出来if (stack.Count > 0){stackTopSymbol = stack.Peek();// 拿栈顶元素出来,但不移除stackTop = Priority(stackTopSymbol);}else break; // 原理同上} while (curPriority<=stackTop);}stack.Push(infixExpression[i]); // 当前的运算符入栈 }}else{stack.Push(infixExpression[i]);}}else{completeDigits += Convert.ToString(infixExpression[i]);}}suffix += completeDigits+",";while (stack.Count>0){suffix += Convert.ToString(stack.Pop())+",";}return suffix;}///<summary>///运算符符号优先级///</summary>///<param name="symbol">运算符符号</param>///<returns></returns>static int Priority(char symbol){switch (symbol){case'*':case'/':return 2;case'+':case'-':return 1;}return -1;}static double Calc(double first, double second, char symbol){switch (symbol){case'*':return (double)first * second;case'/':return (double)first / second;case'+':return (double)first + second;case'-':return (double)first - second;}return 0.0d;}static bool IsOperator(char symbol){char[] symbols={'+','-','*','/','(',')'};return symbols.Contains(symbol);}///<summary>///计算后缀表达式结果///</summary>///<param name="suffixExpression"></param>///<returns></returns>static double CalcSuffix(string[] suffixExpression){Stack<double> stack = new Stack<double>();double temp;for (int i = 0; i < suffixExpression.Length; i++){if (String.IsNullOrWhiteSpace(suffixExpression[i])) break;if (double.TryParse(suffixExpression[i], out temp)) // 是数字 {stack.Push(temp);}else// 是运算符{double rightNum = stack.Pop();double leftNum = stack.Pop();double result = Calc(leftNum, rightNum, Convert.ToChar(suffixExpression[i]));stack.Push(result);}}return stack.Pop();}}}。