下载文档原格式
堆栈和队列Content堆栈1队列2表达式计算3递归4PART THREE表达式计算•表达式的概念•后缀表达式求值•中缀表达式到后缀表达式的转换•中缀表达式：操作符在两个操作数之间的表达式•前缀表达式：操作符在两个操作数之前的表达式•后缀表达式：操作符在两个操作数之后的表达式逆波兰表达式（Reverse Polish notation ，RPN ），J. Lukasiewicz 1929示例：a + b 示例：+ a b 示例：a b +表达式：由操作数、操作符(+、-、*、\等)和界限符（括号等）组成•中缀表达式a + ( b –c )a + ba b +a b c -+计算的顺序由界符、操作符优先级决定计算的顺序只取决于操作符的扫描顺序•后缀表达式VS.对比：•操作数的顺序相同，而操作符的顺序不同；•前者的不同操作符的运算优先级存在差异，后者的所有操作符的运算优先级相同；•前者可以有界限符，后者没有界限符；后缀表达式求值算法(利用堆栈实现):1.从左往右顺序依次扫描后缀表达式中的元素：•若当前扫描元素是操作数，则将操作数进栈；•若当前扫描元素是操作符，则从栈中弹出两个操作数，并执行该操作符指定的运算，然后将计算结果进栈；2.当表达式扫描结束，弹出栈顶数据，该数据即为计算结果。
6 4 2 -/ 3 2 * + 6-24/32*+6/(4-2)+3*2= 9算法(利用堆栈实现):1.从左往右顺序依次扫描后缀表达式中的元素：•若当前扫描元素是操作数，则将操作数进栈；•若当前扫描元素是操作符，则从栈中弹出两个操作数，并执行该操作符指定的运算，然后将计算结果进栈；2.当表达式扫描结束，弹出栈顶数据，该数据即为计算结果。
6 4 2 -/ 3 2 * +6-24/32*+42=2算法(利用堆栈实现):1.从左往右顺序依次扫描后缀表达式中的元素：•若当前扫描元素是操作数，则将操作数进栈；•若当前扫描元素是操作符，则从栈中弹出两个操作数，并执行该操作符指定的运算，然后将计算结果进栈；2.当表达式扫描结束，弹出栈顶数据，该数据即为计算结果。
#include"stdio.h"#include"stdlib.h"#include"malloc.h"typedef struct {char *base;char *top;int stacksize;}SqStackchar;typedef struct {float *base;float *top;int stacksize;}SqStackint;//构造空栈SqStackchar InitStackchar(){SqStackchar S;S.base=(char *)malloc(sizeof(char));if(S.base==NULL) exit(-1);S.top=S.base;S.stacksize=100;return S;}SqStackint InitStackint(){SqStackint S;S.base=(float *)malloc(sizeof(float));if(S.base==NULL) exit(-1);S.top=S.base;S.stacksize=100;return S;}//进栈SqStackchar Pushchar(SqStackchar &S,char c){if((S.top-S.base)==S.stacksize){S.base=(char *)realloc(S.base,110*sizeof(char));if(S.base==NULL) exit(-1);S.top=S.base+S.stacksize;}*S.top++=c;return S;}SqStackint Pushint(SqStackint &S,float c){if((S.top-S.base)==S.stacksize){S.base=(float *)realloc(S.base,110*sizeof(float));if(S.base==NULL) exit(-1);S.top=S.base+S.stacksize;}*S.top++=c;return S;}//获得栈顶元素char GetTopchar(SqStackchar S){char e;if(S.top==S.base) exit(-1);e=*(S.top-1);return e;}float GetTopint(SqStackint S){float e;if(S.top==S.base) exit(-1);e=*(S.top-1);return e;}//出栈操作char Popchar(SqStackchar &S){if(S.top==S.base) exit(-1);char e;e=*--S.top;return e;}float Popint(SqStackint &S){if(S.top==S.base) exit(-1);float e;e=*--S.top;return e;}//判断该字符是数字的还是操作符int In(char c){if(c=='0'||c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7'||c=='8' ||c=='9') return 1;else return 0;}//运算函数float Operate(float a,char theta,float b){switch(theta){case '+':return (a+b);case '-':return (a-b);case '*':return (a*b);case '/':return (a/b);default:exit(-1);}}//判断操作符的优先级char Precede(char a,char b){if((a=='('&&b!=')')||(a=='#'&&b!='#'))return '<';if(a==')')if((a=='('&&b==')')||(a=='#'&&b=='#'))return '=';if((a=='+'||a=='-')&&(b=='+'||b=='-'||b==')'||b=='#'))return '>';if((a=='+'||a=='-')&&(b=='*'||b=='/'||b=='('))return '<';if((a=='*'||a=='/')&&(b=='('))return '<';if((a=='*'||a=='/')&&(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#')) return '>';}//主函数int main(){SqStackchar OPRT;SqStackint OPND;OPRT=InitStackchar();Pushchar(OPRT,'#');OPND=InitStackint();printf("请输入表达式：\n");c=getchar();float a,b;char theta;while(c!='#'||GetTopchar(OPRT)!='#'){if(In(c)){Pushint(OPND,c-48);c=getchar();while(In(c)){float e;e=GetTopint(OPND)*10+(int)(c)-48;Popint(OPND);Pushint(OPND,e);c=getchar();}}elseswitch(Precede(GetTopchar(OPRT),c)){ case '<':Pushchar(OPRT,c);c=getchar();break;case '=':Popchar(OPRT);c=getchar();break;case '>':theta=Popchar(OPRT);b=Popint(OPND);a=Popint(OPND);Pushint(OPND,Operate(a,theta,b));break;}//switch}//whileprintf("结果为：%f\n",GetTopint(OPND));return 0;}Ps.此文章来自网络，供大家学习交流。
逻辑表达式短路求值后缀表达式逻辑表达式短路求值后缀表达式的过程如下：1. 将中缀逻辑表达式转换为后缀表达式。
这个过程可以使用运算符优先级和括号来确定运算符的顺序。
2. 执行后缀表达式的求值过程。
从左到右扫描后缀表达式：- 如果遇到操作数，将其压入栈中。
- 如果遇到操作符，从栈中弹出相应数量的操作数进行运算，并将运算结果压入栈中。
- 重复上述步骤，直到扫描完后缀表达式。
3. 最终栈中剩下的元素就是整个逻辑表达式的求值结果。
例如，对于逻辑表达式 "A && B || C"，其后缀表达式为 "A B&& C ||"。
假设 A = true，B = false，C = true，那么短路求值的过程如下：1. 将 A 和 B 压入栈中。
2. 遇到 "&&" 操作符，从栈中弹出 B（false），然后从栈中弹出 A（true）。
将 A && B 的结果（false）压入栈中。
3. 将 C 压入栈中。
4. 遇到 "||" 操作符，从栈中弹出 C（true），然后从栈中弹出A &&B 的结果（false）。
将 (A && B) ||C 的结果（true）压入栈中。
5. 栈中剩下的元素是最终的结果，即 (A && B) || C 的值为 true。
因此，逻辑表达式 "A && B || C" 的短路求值后缀表达式的结果为 true。
基于栈的后缀算术表达式求值c语言1. 引言1.1 概述本文将讨论基于栈的后缀算术表达式求值的实现过程。
后缀算术表达式（也称为逆波兰表达式）是一种无需括号即可进行运算的表达式表示方法，它将操作符置于操作数之后。
相较于传统的中缀表达式，在计算机程序中处理后缀表达式更为高效和简洁。
1.2 文章结构文章分为五个主要部分：引言、栈的概念及原理、后缀算术表达式的定义和转换、基于栈的后缀算术表达式求值算法实现以及结论与总结。
在引言部分，我们将首先介绍本文的概述和目标，对后续内容进行简要说明。
1.3 目的通过本文，我们旨在让读者了解栈数据结构的基本概念和原理，并且掌握如何利用栈来实现对后缀算术表达式进行求值的算法。
同时，我们将介绍后缀算术表达式的定义和转换方法，并给出基于栈实现该计算方式的详细步骤与示例代码。
通过深入研究并学习这些内容，读者可以加深对栈数据结构和后缀算术表达式的理解，并且能够应用所学知识解决实际问题。
本文不仅适用于计算机科学或相关专业的学生，也适合对数据结构和算法感兴趣的读者阅读和学习。
2. 栈的概念及原理2.1 栈的定义栈是一种具有特定限制条件的线性数据结构，它具备“先进后出”（Last-In-First-Out，LIFO）的特性。
栈可以看作是一个容器，其中可以存储各种类型的数据。
与实际生活中的堆栈类似，栈只允许在其末尾进行插入和删除操作。
在栈中，最后加入的元素首先被访问和处理。
这是由于栈内元素之间的相对位置关系决定的。
插入操作称为“压栈”（Push），删除操作称为“弹栈”（Pop），而从栈顶读取元素或获取栈顶元素但不删除它称为“查看”（Peek）。
2.2 栈的基本操作推入元素：将一个元素添加到栈顶。
如果已经存在满员条件，则无法执行此操作。
弹出元素：从栈顶移除一个元素，并返回移除的值。
如果没有任何元素存在，则无法执行此操作。
查看栈顶元素：获取位于栈顶处的元素值，但不对其进行删除。
判断是否为空：检查栈是否为空。
后缀表达式求值过程嘿，朋友！今天咱们来唠唠后缀表达式求值这个超有趣的事儿。
你可能会想，这后缀表达式是啥呀？就像你看到一个神秘的密码，其实只要掌握了方法，求值就像解开密码锁一样简单又好玩。
我先给你说说啥是后缀表达式吧。
咱平常看到的表达式，像“3 + 4”这种中缀表达式，操作符在中间。
而后缀表达式呢，操作符在操作数的后面，就像“3 4 +”。
这看起来有点怪，可它在计算机处理起来可就方便多啦。
那怎么求值呢？咱得有个小工具，那就是栈。
栈就像一个小盒子，不过这个小盒子有点特别，先放进去的东西后拿出来，就像你往一个窄口瓶子里塞东西，先塞进去的在底下，最后才能拿出来。
比如说咱们要计算“4 5 * 6 +”这个后缀表达式的值。
我和我那聪明的小伙伴小明就开始啦。
小明负责操作栈，我来指挥。
首先看到“4”，小明就把4这个数字放到栈里。
这就像把一个小宝贝放进那个神秘的盒子里。
接着看到“5”，小明也把5放进栈里。
现在栈里就有4和5啦，就像两个小伙伴在盒子里安静地待着。
然后看到“*”这个操作符，这时候就像魔法要开始啦。
小明从栈里拿出5和4（注意哦，是先拿5，因为栈的特性），然后计算4乘以5等于20，再把20放进栈里。
哇，这就像把两个小伙伴融合成了一个超级小伙伴呢！再看到“6”，小明又把6放进栈里。
现在栈里有20和6啦。
最后看到“+”，小明又从栈里拿出6和20，计算20加6等于26，这就是最后的结果啦。
是不是感觉很神奇呢？就像一场奇妙的数学之旅。
再来看一个复杂点的例子吧。
像“3 4 + 2 * 5 -”。
我和我的另一个朋友小花来操作这个。
小花可认真啦。
先看到“3”，放进栈里，再看到“4”，也放进栈里。
看到“+”的时候，小花从栈里拿出4和3，计算3加4等于7，把7放进栈里。
这时候就像我们搭建了一个小积木塔的一部分。
接着看到“2”，放进栈里。
看到“*”的时候，小花从栈里拿出2和7，计算7乘以2等于14，再把14放进栈里。
最后看到“5”，放进栈里，看到“ - ”的时候，小花从栈里拿出5和14，计算14减5等于9。
C#算术表达式求值（后缀法），看这⼀篇就够了⼀、种类介绍算术表达式有三种：前缀表达式、中缀表达式和后缀表达式。
⼀般⽤的是中缀，⽐如1+1，前后缀就是把操作符移到前⾯和后⾯，下⾯简单介绍⼀下这三种表达式。
1、前缀表⽰法前缀表⽰法⼜叫波兰表⽰法，他的操作符置于操作数的前⾯（例：+ 1 2），是波兰数学家扬·武卡谢维奇1920年代引⼊的，⽤于简化命题逻辑。
因为我们⼀般认为操作符是在操作数中间的，所以在⽇常⽣活中⽤的不多，但在计算机科学领域占有⼀席之地。
⼀般的表⽰法对计算机来说处理很⿇烦，每个符号都要考虑优先级，还有括号这种会打乱优先级的存在，将使计算机花费⼤量的资源进⾏解析。
⽽前缀表⽰法没有优先级的概念，他是按顺序处理的。
举个例⼦：9-2*3这个式⼦，计算机需要先分析优先级，先乘后减，找到2*3，再进⾏减操作；化成前缀表⽰法就是：- 9 * 2 3，计算机可以依次读取，操作符作⽤于后⼀个操作数，遇到减就是让9减去后⾯的数，⽽跟着9的是乘，也就是说让9减去乘的结果，这对计算机来说很简单，按顺序来就⾏了。
2、中缀表⽰法这也就是我们⼀般的表⽰法，他的操作符置于操作数的中间（例：1 + 2），前⾯也说过这种⽅法不容易被计算机解析，但他符合⼈们的普遍⽤法，许多编程语⾔也就⽤这种⽅法了。
在中缀表⽰法中括号是必须有的，要不然运算顺序会乱掉。
3、后缀表⽰法后缀表⽰法⼜叫逆波兰表⽰法，他的操作符置于操作数的后⾯（例：1 2 +），他和前缀表⽰法都对计算机⽐较友好，但他很容易⽤堆栈解析，所以在计算机中⽤的很多。
他的解释过程⼀般是：操作数⼊栈；遇到操作符时，操作数出栈，求值，将结果⼊栈；当⼀遍后，栈顶就是表达式的值。
因此逆波兰表达式的求值使⽤堆栈结构很容易实现，且能很快求值。
注意：逆波兰记法并不是简单的波兰表达式的反转。
因为对于不满⾜交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法/ 6 3的逆波兰记法是6 3 /⽽不是3 6 /；数字的数位写法也是常规顺序。
后缀表达式求值实验报告书课程名：数据结构题⽬：后缀表达式求值1、实验题⽬（1)掌握栈“后进先出”的特点。
（2)掌握栈的典型应⽤——后缀表达式求值。
2、实验内容（1）⽤键盘输⼊⼀个整数后缀表达式（操作数的范围是0~9，运算符只含+、—、*、/、，⽽且中间不可以有空格），使⽤循环程序从左向右读⼊表达式。
（2）如果读⼊的是操作数，直接进⼊操作数栈。
（3）如果读⼊的是运算符，⽴即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。
（4）检验程序运⾏结果。
3、实验要求（1）分析后缀表达式求值的算法思想，⽤C（或C++）语⾳设计程序。
（2）上机调试通过实验程序。
（3）给出具体的算法分析，包括时间复杂度和空间复杂度等。
（4）撰写实验报告（把输⼊实验数据及运⾏结果⽤抓图的形式粘贴到实验报告上）。
（5）本程序运⾏结果通过以后，添加到原教材验证性实验3的菜单中去。
4、实验步骤与源程序错误！未找到引⽤源。
实验步骤使⽤循环从左到右输⼊后缀表达式。
如输⼊的是运算符，⽴即从操作数栈取出两个操作数，计算上述操作数和运算符的值，然后存回操作数栈。
如输⼊的是操作数则直接存⼊操作数栈。
整个过程只需要⼀个操作数栈。
由⼀个链栈结点定义node、push（）、pop（）、empty（）运算函数⼀个main（）主函数（完成数据输⼊和函数调⽤）、两个个功能函数：isoperator（）//判运算符getvalue（）//计算表达式值错误！未找到引⽤源。
源代码#include#includestruct node // 栈结构声明{int data; // 数据域struct node *next; // 指针域typedef struct node stacklist; // 链表新类型typedef stacklist *link; // 链表指新针类型link operand=NULL; // 操作数栈指针void push( int value) // 进栈，存⼊数据{link newnode; // 新结点指针newnode=new stacklist; // 分配新结点if (!newnode){printf("分配失败！"); // 存⼊失败return ;}newnode->data=value; // 创建结点的内容newnode->next=operand;operand=newnode; // 新结点成为栈的开始return ;}void pop(int *value) // 出栈，取出数据{link top; // 指向栈顶if (operand !=NULL){top=operand; // 指向栈顶operand=operand->next; // 移动栈顶指针，指向下⼀个结点*value=top->data; // 取数据delete top; // 吸收结点}else*value=-1;}int empty() // 判栈空{if (operand!=NULL) return 1;else return 0;int isoperator(char op) // 判运算符{switch (op){case'+':case'-':case'*':case'/': return 1; // 是运算符，返回default: return 0; // 不是运算符，返回}}int getvalue(int op,int operand1,int operand2) // 计算表达式值{switch((char)op){case'*': return(operand1*operand2);case'/': return(operand1/operand2);case'+': return(operand1+operand2);case'-': return(operand1-operand2);}}void main() // 主函数{char exp[100];int operand1=0; // 定义操作数int operand2=0; // 定义操作数int result=0; // 定义操作结果变量int pos=0; // ⽬前表达式位置printf("\t\n 请输⼊后缀表达式：");gets(exp); //cin.getline(exp,81) // 读取后缀表达式 printf("\t\n\n 后缀表达式[%s]的结果是：",exp); while (exp[pos] !='\0' && exp[pos] !='\n') // 分析表达式字符串{if (isoperator(exp[pos])) // 是运算符，取两个操作数{pop(&operand2);pop(&operand1);push(getvalue(exp[pos],operand1,operand2)); }elsepush(exp[pos]-48); // 是操作数，压⼊操作数栈 pos++; // 移到下⼀个字符串位置}pop(&result); // 弹出结果printf("%d\n",result); // 输出}5、测试数据与实验结果（可以抓图粘贴）图1：程序运⾏结果6、结果分析与实验体会结果分析：本次实验结果准确。
表达式求值算法表达式求值算法是计算机科学中的重要概念之一，用于计算数学表达式的结果。
在编程语言中，表达式求值是一项基本的操作，并且经常在计算过程中需要用到。
本文将介绍一些常见的表达式求值算法及其实现。
1. 逆波兰表达式法逆波兰表达式法是一种用于计算数学表达式的算法，它使用后缀表达式（也称为逆波兰表达式）来表示表达式。
逆波兰表达式是将操作符放在操作数之后的一种表示方法。
对于任意一个数学表达式，都可以通过将中缀表达式转换为后缀表达式，然后使用栈结构计算得到结果。
逆波兰表达式法的优点是计算顺序明确，不需要考虑运算符的优先级和括号的处理。
2. 中缀表达式转后缀表达式法中缀表达式是我们常见的数学表达式，如 3 + 4 * 5。
在中缀表达式中，操作符的优先级和括号起着很大的作用。
为了将中缀表达式转换为后缀表达式，我们需要使用到栈结构。
具体的算法如下：- 遍历中缀表达式的每个元素。
- 如果是操作数，则直接输出。
- 如果是操作符，则判断其与栈顶操作符的优先级，决定是否将其压入栈。
- 如果是左括号，则直接压入栈。
- 如果是右括号，则依次弹出栈顶操作符，并输出，直到遇到左括号为止。
- 遍历完表达式后，如果栈不为空，则依次弹出栈顶操作符，并输出。
3. 后缀表达式求值法后缀表达式（逆波兰表达式）的求值方法相对简单。
我们可以使用栈结构来计算后缀表达式的结果。
具体的算法如下：- 遍历后缀表达式的每个元素。
- 如果是操作数，则将其压入栈。
- 如果是操作符，则弹出栈顶的两个操作数，执行相应的计算，并将结果压入栈。
- 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。
4. 二叉树表示法除了逆波兰表达式法和中缀表达式法，我们还可以使用二叉树来表示表达式，并通过遍历二叉树来计算表达式的结果。
具体的算法如下：- 构建二叉树，将表达式的操作符作为根节点，将操作数作为叶节点。
- 通过后序遍历二叉树，计算出每个子树的值，并将结果返回给其父节点。
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，得到最终结果。
数据结构课程设计第7题yuhao2015-12-30目录1系统分析 (2)1.1项目需求分析 (2)1.2系统功能分析 (2)1.2.1功能函数（Function） (2)1.2.2采用的数据结构介绍 (3)1.3系统需求分析 (3)2系统设计及其实现分析 (4)2.1系统总体设计 (4)2.2系统运行流程图 (4)2.3功能实现分析 (4)3系统测试 (6)4 Bug Report (7)5总结与分析 (7)1系统分析1.1项目需求分析表达式求值是程序设计语言编译中的一个最基本问题，就是将一个表达式转化为逆波兰表达式并求值。
具体要求是以字符序列的形式从终端输入语法正确的，不含变量的整数表达式，并利用给定的优先关系实现对算术四则混合表达式的求值。
要把一个表达式翻译成能正确求值的一个机器指令序列，或者直接对表达式求值，首先要能正确解释表达式。
任何一个表达式都是由操作符，运算符和界限符组成，我们称它们为单词。
一般来说，操作数既可以是常数，又可以是被说明为变量或常量的标识符；运算符可以分成算术运算符，关系运算符和逻辑运算符3类；基本的界限符包括左右括号和表达式结束符等。
为了叙述的简洁，我们仅仅讨论简单算术表达式的求值问题。
这种表达式只包括加，减，乘，除4种运算符。
人们在书写表达式时通常采用的是“中缀”表达形式，也就是将运算符放在两个操作数中间，用这种“中缀”形式表示的表达式称为中缀表达式。
但是，这种表达式表示形式对计算机处理来说是不大合适的。
对于表达式的表示还有另一种形式，称之为“后缀表达式”，也就是将运算符紧跟在两个操作数的后面。
这种表达式比较合适计算机的处理方式，因此要用计算机来处理，计算表达式的问题，首先要将中缀表达式转化成后缀表达式，又称为逆波兰表达式。
所以这次项目的要求为：从控制台读入表达式字符串并将其创建为二叉树，接着分别对二叉树进行前序、中序、后序遍历，分别得到波兰表达式、中缀表达式、逆波兰表达式。
一、设计思想计算算数表达式并求值，采取的共有两种方法：1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。
2.对算数表达式进行直接的计算。
第一种算法这种解决方案又分为两步：1.将表达式先转化为后缀表达式的字符串数组2.利用后缀表达式进行计算在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。
数组中存的就是后缀表达式。
得到后缀表达式后，进行计算，要用到数值栈。
首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。
第二种算发首先要建立两个栈，一个用来存放操作符，一个用来存放数值。
开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。
如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。
如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。
c语言中缀、后缀算术表达式求值用栈实现下面是用栈实现中缀表达式求值的示例代码：#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define MAX_STACK_SIZE 100typedef struct {int top;int data[MAX_STACK_SIZE];} Stack;void init(Stack *s) {s->top = -1;}int is_empty(Stack *s) {return s->top == -1;}int is_full(Stack *s) {return s->top == MAX_STACK_SIZE - 1;}void push(Stack *s, int x) {if (is_full(s)) {printf("Error: stack overflow\n");exit(EXIT_FAILURE);}s->data[++s->top] = x;}int pop(Stack *s) {if (is_empty(s)) {printf("Error: stack underflow\n");exit(EXIT_FAILURE);}return s->data[s->top--];}int peek(Stack *s) {if (is_empty(s)) {printf("Error: stack underflow\n");exit(EXIT_FAILURE);}return s->data[s->top];}int precedence(char op) {switch (op) {case '+':case '-':return 1;case '*':case '/':return 2;default:return 0;}}int evaluate(int op1, int op2, char op) {switch (op) {case '+':return op1 + op2;case '-':return op1 - op2;case '*':return op1 * op2;case '/':return op1 / op2;default:printf("Error: invalid operator\n");exit(EXIT_FAILURE);}}int evaluate_infix(char *expr) {Stack op_stack, val_stack;init(&op_stack);init(&val_stack);while (*expr != '\0') {if (isdigit(*expr)) {int val = 0;while (isdigit(*expr)) {val = val * 10 + (*expr - '0');expr++;}push(&val_stack, val);} else if (*expr == '+' || *expr == '-' || *expr == '*' || *expr == '/') {while (!is_empty(&op_stack) && precedence(peek(&op_stack)) >= precedence(*expr)) {int op2 = pop(&val_stack);int op1 = pop(&val_stack);char op = pop(&op_stack);push(&val_stack, evaluate(op1, op2, op));}push(&op_stack, *expr);expr++;} else if (*expr == '(') {push(&op_stack, '(');expr++;} else if (*expr == ')') {while (peek(&op_stack) != '(') {int op2 = pop(&val_stack);int op1 = pop(&val_stack);char op = pop(&op_stack);push(&val_stack, evaluate(op1, op2, op));}pop(&op_stack);expr++;} else {printf("Error: invalid character\n");exit(EXIT_FAILURE);}}while (!is_empty(&op_stack)) {int op2 = pop(&val_stack);int op1 = pop(&val_stack);char op = pop(&op_stack);push(&val_stack, evaluate(op1, op2, op));}return peek(&val_stack);}int main() {char expr[100];printf("Enter infix expression: ");scanf("%[^\n]", expr);printf("Result = %d\n", evaluate_infix(expr));return 0;}下面是用栈实现后缀表达式求值的示例代码：#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define MAX_STACK_SIZE 100typedef struct {int top;int data[MAX_STACK_SIZE];} Stack;void init(Stack *s) {s->top = -1;}int is_empty(Stack *s) {return s->top == -1;}int is_full(Stack *s) {return s->top == MAX_STACK_SIZE - 1;}void push(Stack *s, int x) {if (is_full(s)) {printf("Error: stack overflow\n");exit(EXIT_FAILURE);}s->data[++s->top] = x;}int pop(Stack *s) {if (is_empty(s)) {printf("Error: stack underflow\n");exit(EXIT_FAILURE);}return s->data[s->top--];}int peek(Stack *s) {if (is_empty(s)) {printf("Error: stack underflow\n");exit(EXIT_FAILURE);}return s->data[s->top];}int evaluate(int op1, int op2, char op) {switch (op) {case '+':return op1 + op2;case '-':return op1 - op2;case '*':return op1 * op2;case '/':return op1 / op2;default:printf("Error: invalid operator\n");exit(EXIT_FAILURE);}}int evaluate_postfix(char *expr) {Stack stack;init(&stack);while (*expr != '\0') {if (isdigit(*expr)) {int val = 0;while (isdigit(*expr)) {val = val * 10 + (*expr - '0');expr++;}push(&stack, val);} else if (*expr == '+' || *expr == '-' || *expr == '*' || *expr == '/') { int op2 = pop(&stack);int op1 = pop(&stack);push(&stack, evaluate(op1, op2, *expr));expr++;} else {printf("Error: invalid character\n");exit(EXIT_FAILURE);}}return peek(&stack);}int main() {char expr[100];printf("Enter postfix expression: ");scanf("%[^\n]", expr);printf("Result = %d\n", evaluate_postfix(expr));return 0;}。
它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。
它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。
举例：(3 + 4) × 5 - 6 就是中缀表达式- × + 3 4 5 6 前缀表达式3 4 + 5 × 6 - 后缀表达式中缀表达式（中缀记法）中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。
中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
对计算机来说，计算前缀或后缀表达式的值非常简单。
前缀表达式（前缀记法、波兰式）前缀表达式的运算符位于操作数之前。
前缀表达式的计算机求值：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如前缀表达式“- × + 3 4 5 6”：(1) 从右至左扫描，将6、5、4、3压入堆栈；(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
可以看出，用计算机计算前缀表达式的值是很容易的。
将中缀表达式转换为前缀表达式：遵循以下步骤：(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2) 从右至左扫描中缀表达式；(3) 遇到操作数时，将其压入S2；(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5) 遇到括号时：(5-1) 如果是右括号“)”，则直接压入S1；(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；(6) 重复步骤(2)至(5)，直到表达式的最左边；(7) 将S1中剩余的运算符依次弹出并压入S2；(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
中缀表达式转换为后缀表达式一、后缀表达式求值后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。
假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：1）遍历表达式，遇到的数字首先放入栈中，此时栈如下所示：2）接着读到“+”，则弹出3和2，执行3+2，计算结果等于5，并将5压入到栈中。
3）读到8，将其直接放入栈中。
4）读到“*”，弹出8和5，执行8*5，并将结果40压入栈中。
而后过程类似，读到“+”，将40和5弹出，将40+5的结果45压入栈...以此类推。
最后求的值288。
二、中缀表达式转后缀表达式2.1）规则中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。
转换过程需要用到栈，具体过程如下：1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。
注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”，“*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。
弹出完这些元素后，才将遇到的操作符压入到栈中。
有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
也就是说这种操作，" + "的优先级最低，" ( "优先级最高。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
2.2）实例规则很多，还是用实例比较容易说清楚整个过程。
以上面的转换为例，输入为a + b * c + (d * e + f)*g，处理过程如下：1）首先读到a，直接输出。
2）读到“+”，将其放入到栈中。
实验报告书
课程名：数据结构
题目：后缀表达式求值
1、实验题目
（1)掌握栈“后进先出”的特点。
（2)掌握栈的典型应用——后缀表达式求值。
2、实验内容
（1）用键盘输入一个整数后缀表达式（操作数的范围是0~9，运算符只含+、—、*、/、，而且中间不可以有空格），使用循环程序从左向右读入表达式。
（2）如果读入的是操作数，直接进入操作数栈。
（3）如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。
（4）检验程序运行结果。
3、实验要求
（1）分析后缀表达式求值的算法思想，用C（或C++）语音设计程序。
（2）上机调试通过实验程序。
（3）给出具体的算法分析，包括时间复杂度和空间复杂度等。
（4）撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。
（5）本程序运行结果通过以后，添加到原教材验证性实验3的菜单中去。
4、实验步骤与源程序
错误！未找到引用源。
实验步骤
使用循环从左到右输入后缀表达式。
如输入的是运算符，立即从操作数栈取出两个操作数，计算上述操作数和运算符的值，然后存回操作数栈。
如输入的是操作数则直接存入操作数栈。
整个过程只需要一个操作数栈。
由一个链栈结点定义node、push（）、pop（）、empty（）运算函数一个main（）主函数（完成数据输入和函数调用）、
两个个功能函数：
isoperator（）//判运算符
getvalue（）//计算表达式值
错误！未找到引用源。
源代码
#include<stdlib.h>
#include<stdio.h>
struct node // 栈结构声明
{
int data; // 数据域
struct node *next; // 指针域
};
typedef struct node stacklist; // 链表新类型
typedef stacklist *link; // 链表指新针类型
link operand=NULL; // 操作数栈指针
void push( int value) // 进栈，存入数据
{
link newnode; // 新结点指针
newnode=new stacklist; // 分配新结点
if (!newnode)
{
printf("分配失败！"); // 存入失败
return ;
}
newnode->data=value; // 创建结点的内容
newnode->next=operand;
operand=newnode; // 新结点成为栈的开始
return ;
}
void pop(int *value) // 出栈，取出数据
{
link top; // 指向栈顶
if (operand !=NULL)
{
top=operand; // 指向栈顶
operand=operand->next; // 移动栈顶指针，指向下一个结点
*value=top->data; // 取数据
delete top; // 吸收结点
}
else
*value=-1;
}
int empty() // 判栈空
{
if (operand!=NULL) return 1;
else return 0;
}
int isoperator(char op) // 判运算符
{
switch (op)
{
case'+':
case'-':
case'*':
case'/': return 1; // 是运算符，返回
default: return 0; // 不是运算符，返回
}
}
int getvalue(int op,int operand1,int operand2) // 计算表达式值
{
switch((char)op)
{
case'*': return(operand1*operand2);
case'/': return(operand1/operand2);
case'+': return(operand1+operand2);
case'-': return(operand1-operand2);
}
}
void main() // 主函数
{
char exp[100];
int operand1=0; // 定义操作数
int operand2=0; // 定义操作数
int result=0; // 定义操作结果变量
int pos=0; // 目前表达式位置
printf("\t\n 请输入后缀表达式：");
gets(exp); //cin.getline(exp,81) // 读取后缀表达式 printf("\t\n\n 后缀表达式[%s]的结果是：",exp);
while (exp[pos] !='\0' && exp[pos] !='\n') // 分析表达式字符串
{
if (isoperator(exp[pos])) // 是运算符，取两个操作数
{
pop(&operand2);
pop(&operand1);
push(getvalue(exp[pos],operand1,operand2)); }
else
push(exp[pos]-48); // 是操作数，压入操作数栈 pos++; // 移到下一个字符串位置
}
pop(&result); // 弹出结果
printf("%d\n",result); // 输出
}
5、测试数据与实验结果（可以抓图粘贴）
图1：程序运行结果
6、结果分析与实验体会
结果分析：
本次实验结果准确。
按照题目要求得出结果了。
算法分析：
设后缀表达式长度为n，
程序中的栈运算时间复杂度都为：O（1）；
功能函数的时间复杂度也都为：O（1）
主函数复杂度都是为：O（n）；
所以总时间复杂度都是为：O（n）；
总空间复杂度都是为：O（n）；
实验体会：
通过了运用课堂所学的知识以及课外的相关知识学习，我掌握了在顺序栈和链栈上实现进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。
栈是限制在表尾进行插入和删除操作的线性表。
体会到栈的逻辑结构和线性表相同，其主要特性是“后进先出”；熟悉了栈在计算机的软件设计中的各种应用，能灵活应用栈的基本原理解决一些综合性的应用问题。
不过在运行中间出现了点错误，经过思考和与同学的商量完成了这次的设计，在学习的过程中我觉得一定要多看书本和翻阅课外资料才能够学好数据结构这门课程。
