目錄:
1.前中后綴表達(dá)式的概述
2.中序表達(dá)式轉(zhuǎn)前后綴表達(dá)式
3.運(yùn)用棧的后綴表達(dá)式實(shí)現(xiàn)計(jì)算器原理步驟
4.代碼實(shí)現(xiàn)和分析

1.前中后綴表達(dá)式的概述及相互轉(zhuǎn)換

• 前綴表達(dá)式：運(yùn)算符位于操作數(shù)之前。
• 中綴表達(dá)式（波蘭式）：首先前中后綴表達(dá)式，一般正常寫的(2*4-1)+5-6這種式子稱為中綴表達(dá)式。
• 后綴表達(dá)式（逆波蘭式）：運(yùn)算符位于操作數(shù)之前。

我們平時(shí)所看到的中綴表達(dá)式，計(jì)算機(jī)是不能直接拿來(lái)運(yùn)算的，因?yàn)橛?jì)算機(jī)不知道該如何計(jì)算，然而計(jì)算機(jī)能知道該如何計(jì)算前后綴表達(dá)式。這就是前后綴表達(dá)式的意義

前綴和后綴表達(dá)式中是不含括號(hào)的

2.中序表達(dá)式轉(zhuǎn)前后綴表達(dá)式

2.1中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

其實(shí)轉(zhuǎn)換的原理就是：

從左到右依次遍歷每個(gè)數(shù)字和字符，若是數(shù)字就輸出，成為后綴表達(dá)式的一部分，若是符號(hào)，判斷與棧頂元素的優(yōu)先級(jí)，是右括號(hào)或優(yōu)先級(jí)不高于棧頂符號(hào)(乘除優(yōu)先于加減)則棧頂元素依次出棧成為后綴表達(dá)式的一部分，再將當(dāng)前符號(hào)進(jìn)棧，直到最終后綴表達(dá)式輸出完畢。

幾個(gè)注意點(diǎn)：

• 同等級(jí)的運(yùn)算符比如+，先進(jìn)的+的優(yōu)先級(jí)大于之后進(jìn)棧的+優(yōu)先級(jí)
• 一個(gè)元素進(jìn)棧，必須匹配優(yōu)先級(jí)比自己低的元素才能進(jìn)，否則比它高的符號(hào)都彈出來(lái)作為表達(dá)式的一部分自己再進(jìn)棧，比如：棧有兩個(gè)元素，棧底為+，然后*在+上邊，那么此時(shí)-進(jìn)棧，由于此時(shí)的+和 *的優(yōu)先級(jí)都比-高，所以兩個(gè)都彈出來(lái)變成表達(dá)式的一部分自己再進(jìn)棧
• 左括號(hào)比所有括號(hào)外邊的符號(hào)優(yōu)先級(jí)高，比括號(hào)里邊的所有符號(hào)都低
• 當(dāng)一個(gè)右括號(hào)進(jìn)棧后，與自己最近的左括號(hào)之間的所有元素彈出成為表達(dá)式的一部分，然后左右括號(hào)抵消

舉個(gè)例子(S1是存放運(yùn)算符的棧，S2是存放生成的后綴表達(dá)式的棧)：

2.2中綴表達(dá)式轉(zhuǎn)前綴表達(dá)式：

其實(shí)和前面差不多，和轉(zhuǎn)后綴表達(dá)式有五個(gè)不同點(diǎn)

• 中綴表達(dá)式轉(zhuǎn)前綴表達(dá)式是自右向左掃描的
• 右括號(hào)比所有括號(hào)外邊的符號(hào)優(yōu)先級(jí)高，比括號(hào)里邊的所有符號(hào)都低
• 當(dāng)一個(gè)左括號(hào)進(jìn)棧后，與自己最近的右括號(hào)之間的所有元素彈出成為表達(dá)式的一部分，然后左右括號(hào)抵消
• 中綴轉(zhuǎn)后綴還有一個(gè)不一樣的是，棧頂與當(dāng)前遇到的新的運(yùn)算符屬于同級(jí)運(yùn)算符時(shí)，棧頂即要出棧，因?yàn)槭峭?jí)先算左邊；然后中綴轉(zhuǎn)前綴由于是右到左遍歷的，所以同級(jí)運(yùn)算符不出棧，因?yàn)槌鰲t代表最后的結(jié)果要先算右邊
• 得到的表達(dá)式倒置就是我們需要的前綴表達(dá)式

還拿1+((2+3)*4)-5舉例子：

3.運(yùn)用棧的后綴表達(dá)式實(shí)現(xiàn)計(jì)算器原理步驟

3.1后綴表達(dá)式實(shí)現(xiàn)計(jì)算器原理

程序初始化兩個(gè)棧，一個(gè)是OPTR(運(yùn)算符棧)，一個(gè)是OPND(操作數(shù)棧)，然后掃描表達(dá)式，一個(gè)一個(gè)的讀入字符。在把我們輸入的中綴表達(dá)式裝換成后綴表達(dá)式的同時(shí)進(jìn)行計(jì)算

程序是如何邊轉(zhuǎn)換邊計(jì)算呢，比如9+(3-1)*3,我們從左到右掃描，那么OPTR和OPND兩個(gè)棧的元素變化如下

掃描到的元素OPND棧OPTR棧

9	9	空
+	9	+
(	9	+(
3	93	+(
-	93	+(-
1	931	+(-
)	92	+
*	92	+*
3	923	+*
無(wú)元素可以掃描	96	+
無(wú)元素可以掃描	15(最終結(jié)果)	空

可以發(fā)現(xiàn)只要彈出一個(gè)運(yùn)算符就會(huì)在操作數(shù)棧中彈出兩個(gè)操作數(shù)，先出來(lái)的在右后出來(lái)的在左，讓彈出來(lái)的運(yùn)算符對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算，計(jì)算完畢后壓入操作數(shù)棧中

3.2后綴表達(dá)式實(shí)現(xiàn)計(jì)算器原理的步驟

我們的程序是不會(huì)知道你輸入的表達(dá)式是否開始和結(jié)束，那么此時(shí)我們使用#來(lái)表示輸入開始和結(jié)束，比如我們想計(jì)算2+2，那么就需要輸入2+2#(我們可以在初始化的時(shí)候把起始的#壓入運(yùn)算符棧)然后回車，讓我們的程序計(jì)算。計(jì)算的過程是：程序初始化兩個(gè)棧，一個(gè)是OPTR(運(yùn)算符棧)，一個(gè)是OPND(操作數(shù)棧)，然后掃描表達(dá)式，一個(gè)一個(gè)的讀入字符(我們把數(shù)字和操作符都看成字符)，，如果表達(dá)式?jīng)]有掃描完畢(即沒有遇到#)或者說OPTR的棧頂元素不為#時(shí)則循環(huán)執(zhí)行下面的操作：
1.若字符不是運(yùn)算符，則壓入OPND棧中，讀入下一個(gè)字符
2.若字符是運(yùn)算符則根據(jù)OPTR的棧頂元素和新掃描的字符的優(yōu)先級(jí)比較結(jié)果，做不同的處理
? ?(1)若是小于，則ch壓入OPTR棧，再讀入下一個(gè)字符
? ?(2)若是大于，則彈出OPTR棧頂?shù)倪\(yùn)算符，從OPND棧彈出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果壓入OPND棧
? ?(3)若是等于，則OPTR的棧頂元素是“（”且新掃描的字符為“)”，這時(shí)彈出OPTR棧頂?shù)摹?”相當(dāng)于括號(hào)匹配成功，然后讀入下一個(gè)字符

4. 代碼實(shí)現(xiàn)和分析

#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;//構(gòu)造一個(gè)空棧 Status InitStack(LinkStack &S) {S = NULL;return OK; }//判斷是否為空棧 bool StackEmpty(LinkStack S) {if (!S)return true;return false; }//用e返回S的項(xiàng)元素 Status GetTop(LinkStack &S) {if (!S)return ERROR;return S->data; }//插入e為新的項(xiàng)元素 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的項(xiàng)元素，并用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; }/*判斷輸入的某個(gè)字符是否是運(yùn)算符*ch表示輸入的字符*oper數(shù)組中存放系統(tǒng)能識(shí)別的運(yùn)算符*/ bool In(char ch) {for (int i = 0; i < 7; i++) {if (ch == oper[i]) {return true;}}return false; }/*比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)*a，b中存放待比較的運(yùn)算符*/ char Precede(char a, char b) {if ((a == '(' && b == ')') || (a == '#' && b == '#')) {return '=';} else if (a == '(' || a == '#' || b == '(' || (a == '+' || a == '-') && (b == '*' || b == '/')) {return '<';} elsereturn '>'; }/*進(jìn)行兩數(shù)的運(yùn)算*a，b中分別以char型存放兩個(gè)待運(yùn)算的操作數(shù)*theta中存放代表操作符的字符*結(jié)果以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　表達(dá)式求值 char EvaluateExpression() {//算術(shù)表達(dá)式求值的算符優(yōu)先算法，設(shè)OPTR和OPND分別為運(yùn)算符棧和操作數(shù)棧LinkStack OPTR, OPND;char ch, theta, a, b, x, top;InitStack(OPND); //初始化OPND操作數(shù)棧InitStack(OPTR); //初始化OPTR運(yùn)算符棧Push(OPTR, '#'); //將表達(dá)式起始符“#”壓入OPTR棧scanf("%c",&ch);while (ch != '#' || (GetTop(OPTR) != '#')) //表達(dá)式?jīng)]有掃描完畢或OPTR的棧頂元素不為“#”{if (!In(ch)) {Push(OPND, ch);scanf("%c",&ch);} //ch不是運(yùn)算符則進(jìn)OPND棧elseswitch (Precede(GetTop(OPTR), ch)) //比較OPTR的棧頂元素和ch的優(yōu)先級(jí){case '<': //棧頂元素優(yōu)先級(jí)低Push(OPTR, ch);scanf("%c",&ch); //當(dāng)前字符ch壓入OPTR棧，讀入下一字符chbreak;case '>':Pop(OPTR, theta); //彈出OPTR棧頂?shù)倪\(yùn)算符Pop(OPND, b);Pop(OPND, a); //彈出OPND棧頂?shù)膬蓚€(gè)運(yùn)算數(shù)Push(OPND, Operate(a, theta, b)); //將運(yùn)算結(jié)果壓入OPND棧break;case '=': //OPTR的棧頂元素是“(”且ch是“)”Pop(OPTR, x);scanf("%c",&ch); //彈出OPTR棧頂?shù)摹?”，讀入下一字符chbreak;} //switch} //whilereturn GetTop(OPND); //OPND棧頂元素即為表達(dá)式求值結(jié)果 }int menu() {int c;printf("0-9以內(nèi)的多項(xiàng)式計(jì)算\n" );printf("1.計(jì)算\n");printf("0.退出\n");printf("選擇：");scanf("%d",&c);return c; }int main() {do{switch (menu()) {case 1: {printf("請(qǐng)輸入要計(jì)算的表達(dá)式（操作數(shù)和結(jié)果都在0-9的范圍內(nèi)，以#結(jié)束）：\n如 2+2# \n" );char res = EvaluateExpression();//算法3.22　表達(dá)式求值printf("計(jì)算結(jié)果為%d\n",res - 48);printf("--------------------------------------\n");}break;case 0:printf("退出成功\n");return 0;default:break;}}while (1);return 0; }

例子：

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的前、中、后缀表达式概述及转换+栈的计算器原理及代码分析(含完整源码)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。