目录:
1.前中后缀表达式的概述
2.中序表达式转前后缀表达式
3.运用栈的后缀表达式实现计算器原理步骤
4.代码实现和分析

1.前中后缀表达式的概述及相互转换

• 前缀表达式：运算符位于操作数之前。
• 中缀表达式（波兰式）：首先前中后缀表达式，一般正常写的(2*4-1)+5-6这种式子称为中缀表达式。
• 后缀表达式（逆波兰式）：运算符位于操作数之前。

我们平时所看到的中缀表达式，计算机是不能直接拿来运算的，因为计算机不知道该如何计算，然而计算机能知道该如何计算前后缀表达式。这就是前后缀表达式的意义

前缀和后缀表达式中是不含括号的

2.中序表达式转前后缀表达式

2.1中缀表达式转后缀表达式

其实转换的原理就是：

从左到右依次遍历每个数字和字符，若是数字就输出，成为后缀表达式的一部分，若是符号，判断与栈顶元素的优先级，是右括号或优先级不高于栈顶符号(乘除优先于加减)则栈顶元素依次出栈成为后缀表达式的一部分，再将当前符号进栈，直到最终后缀表达式输出完毕。

几个注意点：

• 同等级的运算符比如+，先进的+的优先级大于之后进栈的+优先级
• 一个元素进栈，必须匹配优先级比自己低的元素才能进，否则比它高的符号都弹出来作为表达式的一部分自己再进栈，比如：栈有两个元素，栈底为+，然后*在+上边，那么此时-进栈，由于此时的+和 *的优先级都比-高，所以两个都弹出来变成表达式的一部分自己再进栈
• 左括号比所有括号外边的符号优先级高，比括号里边的所有符号都低
• 当一个右括号进栈后，与自己最近的左括号之间的所有元素弹出成为表达式的一部分，然后左右括号抵消

举个例子(S1是存放运算符的栈，S2是存放生成的后缀表达式的栈)：

2.2中缀表达式转前缀表达式：

其实和前面差不多，和转后缀表达式有五个不同点

• 中缀表达式转前缀表达式是自右向左扫描的
• 右括号比所有括号外边的符号优先级高，比括号里边的所有符号都低
• 当一个左括号进栈后，与自己最近的右括号之间的所有元素弹出成为表达式的一部分，然后左右括号抵消
• 中缀转后缀还有一个不一样的是，栈顶与当前遇到的新的运算符属于同级运算符时，栈顶即要出栈，因为是同级先算左边；然后中缀转前缀由于是右到左遍历的，所以同级运算符不出栈，因为出栈则代表最后的结果要先算右边
• 得到的表达式倒置就是我们需要的前缀表达式

还拿1+((2+3)*4)-5举例子：

3.运用栈的后缀表达式实现计算器原理步骤

3.1后缀表达式实现计算器原理

程序初始化两个栈，一个是OPTR(运算符栈)，一个是OPND(操作数栈)，然后扫描表达式，一个一个的读入字符。在把我们输入的中缀表达式装换成后缀表达式的同时进行计算

程序是如何边转换边计算呢，比如9+(3-1)*3,我们从左到右扫描，那么OPTR和OPND两个栈的元素变化如下

扫描到的元素OPND栈OPTR栈

9	9	空
+	9	+
(	9	+(
3	93	+(
-	93	+(-
1	931	+(-
)	92	+
*	92	+*
3	923	+*
无元素可以扫描	96	+
无元素可以扫描	15(最终结果)	空

可以发现只要弹出一个运算符就会在操作数栈中弹出两个操作数，先出来的在右后出来的在左，让弹出来的运算符对两个操作数进行计算，计算完毕后压入操作数栈中

3.2后缀表达式实现计算器原理的步骤

我们的程序是不会知道你输入的表达式是否开始和结束，那么此时我们使用#来表示输入开始和结束，比如我们想计算2+2，那么就需要输入2+2#(我们可以在初始化的时候把起始的#压入运算符栈)然后回车，让我们的程序计算。计算的过程是：程序初始化两个栈，一个是OPTR(运算符栈)，一个是OPND(操作数栈)，然后扫描表达式，一个一个的读入字符(我们把数字和操作符都看成字符)，，如果表达式没有扫描完毕(即没有遇到#)或者说OPTR的栈顶元素不为#时则循环执行下面的操作：
1.若字符不是运算符，则压入OPND栈中，读入下一个字符
2.若字符是运算符则根据OPTR的栈顶元素和新扫描的字符的优先级比较结果，做不同的处理
   (1)若是小于，则ch压入OPTR栈，再读入下一个字符
   (2)若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈
   (3)若是等于，则OPTR的栈顶元素是“（”且新扫描的字符为“)”，这时弹出OPTR栈顶的“(”相当于括号匹配成功，然后读入下一个字符

4. 代码实现和分析

#include<stdio.h> const char oper[7] = { '+', '-', '*', '/', '(', ')', '#' }; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char SElemType; typedef int Status; typedef struct SNode {int data;struct SNode *next; } SNode, *LinkStack;//构造一个空栈 Status InitStack(LinkStack &S) {S = NULL;return OK; }//判断是否为空栈 bool StackEmpty(LinkStack S) {if (!S)return true;return false; }//用e返回S的项元素 Status GetTop(LinkStack &S) {if (!S)return ERROR;return S->data; }//插入e为新的项元素 Status Push(LinkStack &S, SElemType e) {SNode *p = new SNode;if (!p) {return OVERFLOW;}p->data = e;p->next = S;S = p;return OK; }//删除S的项元素，并用e返回其值 Status Pop(LinkStack &S, SElemType &e) {SNode *p;if (!S)return ERROR;e = S->data;p = S;S = S->next;delete p;return OK; }/*判断输入的某个字符是否是运算符*ch表示输入的字符*oper数组中存放系统能识别的运算符*/ bool In(char ch) {for (int i = 0; i < 7; i++) {if (ch == oper[i]) {return true;}}return false; }/*比较两个运算符的优先级*a，b中存放待比较的运算符*/ char Precede(char a, char b) {if ((a == '(' && b == ')') || (a == '#' && b == '#')) {return '=';} else if (a == '(' || a == '#' || b == '(' || (a == '+' || a == '-') && (b == '*' || b == '/')) {return '<';} elsereturn '>'; }/*进行两数的运算*a，b中分别以char型存放两个待运算的操作数*theta中存放代表操作符的字符*结果以char型返回*/ char Operate(char a, char theta, char b) {switch (theta) {case '+':return (a - '0') + (b - '0') + 48;case '-':return (a - '0') - (b - '0') + 48;case '*':return (a - '0') * (b - '0') + 48;case '/':return (a - '0') / (b - '0') + 48;}return 0; }//算法3.22　表达式求值 char EvaluateExpression() {//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈LinkStack OPTR, OPND;char ch, theta, a, b, x, top;InitStack(OPND); //初始化OPND操作数栈InitStack(OPTR); //初始化OPTR运算符栈Push(OPTR, '#'); //将表达式起始符“#”压入OPTR栈scanf("%c",&ch);while (ch != '#' || (GetTop(OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”{if (!In(ch)) {Push(OPND, ch);scanf("%c",&ch);} //ch不是运算符则进OPND栈elseswitch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级{case '<': //栈顶元素优先级低Push(OPTR, ch);scanf("%c",&ch); //当前字符ch压入OPTR栈，读入下一字符chbreak;case '>':Pop(OPTR, theta); //弹出OPTR栈顶的运算符Pop(OPND, b);Pop(OPND, a); //弹出OPND栈顶的两个运算数Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈break;case '=': //OPTR的栈顶元素是“(”且ch是“)”Pop(OPTR, x);scanf("%c",&ch); //弹出OPTR栈顶的“(”，读入下一字符chbreak;} //switch} //whilereturn GetTop(OPND); //OPND栈顶元素即为表达式求值结果 }int menu() {int c;printf("0-9以内的多项式计算\n" );printf("1.计算\n");printf("0.退出\n");printf("选择：");scanf("%d",&c);return c; }int main() {do{switch (menu()) {case 1: {printf("请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：\n如 2+2# \n" );char res = EvaluateExpression();//算法3.22　表达式求值printf("计算结果为%d\n",res - 48);printf("--------------------------------------\n");}break;case 0:printf("退出成功\n");return 0;default:break;}}while (1);return 0; }

例子：

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的前、中、后缀表达式概述及转换+栈的计算器原理及代码分析(含完整源码)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。