Hello，大家好，國(guó)慶的第二天，帶來(lái)的是數(shù)據(jù)結(jié)構(gòu)中堆棧部分的后綴表達(dá)式，這也是一塊有關(guān)棧的應(yīng)用方面困擾了眾多同學(xué)的一個(gè)大難題，今天就讓我們一起解決這個(gè)難題??

?初見(jiàn)：什么是后綴表達(dá)式

后綴表達(dá)式也稱(chēng)為逆波蘭表達(dá)式，也就是將算術(shù)運(yùn)算符放在操作數(shù)的后面

• 例如【1 + 2 * 3】的后綴表達(dá)式形式變?yōu)椤? 2 3 * +】，前面的那個(gè)叫做中綴表達(dá)式，也就是我們最常用的，遵循的規(guī)則是“先乘除，后加減”；
• 那有些小伙伴就很疑惑，為什么要這么去做呢，好好地用我門(mén)正常的計(jì)算形式去運(yùn)算不就好了，下面我們就來(lái)講講后綴表達(dá)式

后綴表達(dá)式的優(yōu)勢(shì)

• 對(duì)于后綴表達(dá)式，它十分地有用，因?yàn)槠淇梢园?strong>復(fù)雜的表達(dá)式轉(zhuǎn)化為依靠簡(jiǎn)單操作得到的計(jì)算結(jié)果的表達(dá)式。就我們上面這個(gè)表達(dá)式來(lái)看，是非常簡(jiǎn)單的，但如果換一個(gè)復(fù)雜一些的呢，你能夠在短期時(shí)間內(nèi)把它計(jì)算出來(lái)嗎??

• 可以看出，對(duì)于這個(gè)中綴表達(dá)式，是比較復(fù)雜的，但是我們利用后綴表達(dá)式去簡(jiǎn)化，看起來(lái)就沒(méi)有這么復(fù)雜了，利用這個(gè)表達(dá)式與堆棧的先進(jìn)后出【FILO】原理，就可以達(dá)到事半而功倍的效果

??磨礪：怎樣將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式【?????】

相信這部分是大家最難過(guò)的一道坎，讓我們來(lái)一探究竟??

??熟悉規(guī)則【重點(diǎn)基礎(chǔ)掌握】

首先，最重要的一點(diǎn)是你必須知道轉(zhuǎn)換的規(guī)則

??法則一：如果遇到一個(gè)運(yùn)算符op以及左括號(hào)“（”，此時(shí)棧如果為空，則直接將其進(jìn)棧
??法則二：若是遇到了操作數(shù)num，就將其直接輸出
??法則三：如果棧不為空，則只有當(dāng)op的優(yōu)先級(jí)高于棧頂運(yùn)算符優(yōu)先級(jí)時(shí)才將其進(jìn)棧，否則將棧頂op彈出
??法則四：若當(dāng)前op進(jìn)棧時(shí)發(fā)現(xiàn)棧中有與之相同op，則出棧其一，再加當(dāng)前op壓入棧中
??法則五：若遇到右括號(hào)，則開(kāi)始彈出棧字符，直到左括號(hào)為止
??法則六：只要當(dāng)遇到右括號(hào)“）”時(shí)，才從棧中彈出左括號(hào)“（”，否則一直遍歷

• 以上法則是我們要了解后綴表達(dá)式轉(zhuǎn)換的基本，你必須將其記牢

??層層剖析【堆棧原理展示】

有了固定的發(fā)展，接下來(lái)就是具體的案例和分析

• 我們以此表達(dá)式為例進(jìn)行講解【5 + 8*2 + ( 3 * 9 + 6 )*4】

Part1

• 首先是5，根據(jù)法則二，直接放入表達(dá)式
• 然后是操作符【+】，根據(jù)法則一，棧為空，直接入棧
• 接著是8，同理，直接放入表達(dá)式
• 其次是操作符【*】，因優(yōu)先級(jí)高于【+】，故直接入棧
• 最后又碰到一個(gè)2，同理，直接放入表達(dá)式

Part2
【5 + 8*2 + ( 3 * 9 + 6 )*4】

• 讀到【+】，這時(shí)要注意，引起優(yōu)先級(jí)低于【*】，所以乘號(hào)出棧，放入表達(dá)式，但此時(shí)遍歷到的操作符op與棧中的【+】一致，故棧中的【+】也因放入表達(dá)式，接著將遍歷到的【+】入棧

Part3
【5 + 8*2 + ( 3 * 9 + 6 )*4】

• 首先讀到左括號(hào)【(】，這代表一個(gè)子表達(dá)式的開(kāi)始，因其優(yōu)先級(jí)最高，故直接入棧
• 然后是3，根據(jù)法則二，直接放入表達(dá)式
• 接著遇到【*】，此時(shí)要注意，根據(jù)法則六，因?yàn)檫€沒(méi)有碰到右括號(hào)【)】，說(shuō)明子表達(dá)式還沒(méi)結(jié)束，故直接入棧
• 最后是9，同理，放入表達(dá)式

Part4
【5 + 8*2 + ( 3 * 9 + 6 )*4】

• 首先我們遇到【+】，這是看到棧頂op為【*】，比其低，根據(jù)法則三，彈出棧頂元素，并將當(dāng)前op入棧
• 然后是6，根據(jù)法則二，直接放入表達(dá)式
• 最后讀到【)】，表示子表達(dá)式結(jié)束，開(kāi)始逐個(gè)彈出棧頂元素，直到左括號(hào)【(】彈出后結(jié)束（括號(hào)均不放入表達(dá)式）

Part5
【5 + 8*2 + ( 3 * 9 + 6 )*4】

• 碰到【*】，因其優(yōu)先級(jí)高于棧中的【+】，故直接入棧
• 然后是4，根據(jù)法則二，直接放入表達(dá)式

Part6
【5 + 8*2 + ( 3 * 9 + 6 )*4】

• 最后遍歷到末尾，棧中還有兩個(gè)操作符op，直接彈出即可（不放入表示式）

• 最后的postexp即為轉(zhuǎn)換后的后綴表達(dá)式【582*+39*6+4】

??手撕代碼【不信你看不懂】

了解了堆棧的基本原理后，接下來(lái)就是代碼環(huán)節(jié)，也是可視化計(jì)算的重要一趴

void trans(char* exp, char postexp[])	//將算術(shù)表達(dá)式exp轉(zhuǎn)換成后綴表達(dá)式postexp
{
	char e;
	SqStack* Optr;						//定義運(yùn)算符棧
	InitStack(Optr);					//初始化運(yùn)算符棧
	int i = 0;							//i作為postexp的下標(biāo)
	while (*exp != '\0')					//exp表達(dá)式未掃描完時(shí)循環(huán)
	{
		switch (*exp)
		{
		case '(':						//判定為左括號(hào)
			Push(Optr, '(');				//左括號(hào)進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		case ')':						//判定為右括號(hào)
			Pop(Optr, e);				//出棧元素e
			while (e != '(')				//不為'('時(shí)循環(huán)
			{
				postexp[i++] = e;			//將e存放到postexp中
				Pop(Optr, e);			//繼續(xù)出棧元素e
			}
			exp++;						//繼續(xù)掃描其他字符
			break;
		case '+':						//判定為加或減號(hào)
		case '-':
			while (!StackEmpty(Optr))	//棧不空循環(huán)
			{
				GetTop(Optr, e);			//取棧頂元素e
				if (e != '(')				//e不是'('
				{
					postexp[i++] = e;		//將e存放到postexp中
					Pop(Optr, e);		//出棧元素e
				}
				else					//e是'(時(shí)退出循環(huán)
					break;
			}
			Push(Optr, *exp);			//將'+'或'-'進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		case '*':						//判定為'*'或'/'號(hào)
		case '/':
			while (!StackEmpty(Optr))	//棧不空循環(huán)
			{
				GetTop(Optr, e);			//取棧頂元素e
				if (e == '*' || e == '/')	//將棧頂'*'或'/'運(yùn)算符出棧并存放到postexp中
				{
					postexp[i++] = e;		//將e存放到postexp中
					Pop(Optr, e);		//出棧元素e
				}
				else					//e為非'*'或'/'運(yùn)算符時(shí)退出循環(huán)
					break;
			}
			Push(Optr, *exp);			//將'*'或'/'進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		default:				//處理數(shù)字字符
			while (*exp >= '0' && *exp <= '9') //判定為數(shù)字
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = ' ';	//用#標(biāo)識(shí)一個(gè)數(shù)值串結(jié)束
		}
	}
	while (!StackEmpty(Optr))	//此時(shí)exp掃描完畢,棧不空時(shí)循環(huán)
	{
		Pop(Optr, e);			//出棧元素e
		postexp[i++] = e;			//將e存放到postexp中
	}
	postexp[i] = '\0';			//給postexp表達(dá)式添加結(jié)束標(biāo)識(shí)
	DestroyStack(Optr);			//銷(xiāo)毀棧		
}

看完這串代碼，不用猜，我知道你已經(jīng)已經(jīng)想點(diǎn)下瀏覽器中這個(gè)網(wǎng)頁(yè)的【×】了。但是何妨不聽(tīng)我講完再說(shuō)

• 這里我們需要用到順序的結(jié)構(gòu)實(shí)現(xiàn)原理SqStack，代碼在最后給出，這里就展示轉(zhuǎn)換的算法部分
• 整體瀏覽，這串代碼處于一個(gè)while循環(huán)之中，也就是對(duì)給出的字符串進(jìn)行的一個(gè)遍歷，【!= ‘\0’】在C語(yǔ)言中表示還沒(méi)到字符串結(jié)尾
• 在大層的while循環(huán)之下是一個(gè)switch()分支判斷，判斷的就是當(dāng)前所遍歷的exp，在英文中是expression【表達(dá)式】，上面講到的postexp就是postexpression【后綴表達(dá)式】，我們的目的就是要去exp中遍歷每一個(gè)字符，然后將符合條件的字符按照后綴表達(dá)式的法則以及堆棧的原理一個(gè)個(gè)地放入postexp中，然后我們來(lái)分別說(shuō)說(shuō)每個(gè)case的判斷
• 首先是左括號(hào)【(】，這個(gè)直接進(jìn)棧即可，exp++表示將遍歷下一個(gè)字符，break表示的跳出當(dāng)前的case分支，若是不寫(xiě)這一句，則程序會(huì)一直往下走，直到下一個(gè)break才會(huì)跳出

case '(':						//判定為左括號(hào)
	Push(Optr, '(');				//左括號(hào)進(jìn)棧
	exp++;						//繼續(xù)掃描其他字符
	break;

• 接著是右括號(hào)【)】，上面說(shuō)過(guò)了，若是碰到右括號(hào)，則開(kāi)始出棧棧頂元素，知道棧頂元素為左括號(hào)【(】時(shí)，while體中的語(yǔ)句就是將當(dāng)前出棧的元素放入postexp后綴表達(dá)式中，i++表示為下一個(gè)位置留出位置，然后Pop出棧即可，循環(huán)結(jié)束后繼續(xù)掃描下一個(gè)字符

case ')':						//判定為右括號(hào)
	Pop(Optr, e);				//出棧元素e
	while (e != '(')				//不為'('時(shí)循環(huán)
	{
		postexp[i++] = e;			//將e存放到postexp中
		Pop(Optr, e);			//繼續(xù)出棧元素e
	}
	exp++;						//繼續(xù)掃描其他字符
	break;

• 然后是【+】【-】，它們的循環(huán)條件是棧不為空，首先去獲取棧頂元素，若獲取的元素不為左括號(hào)【(】，則表示子表達(dá)式?jīng)]結(jié)束，不停地將棧頂元素放入postexp中，然后出棧。若是碰到了左括號(hào)【(】，則跳出當(dāng)前循環(huán)，循環(huán)后將當(dāng)前的【+】【-】入棧，繼續(xù)掃描下一個(gè)字符

case '+':						//判定為加或減號(hào)
case '-':
	while (!StackEmpty(Optr))	//棧不空循環(huán)
	{
		GetTop(Optr, e);			//取棧頂元素e
		if (e != '(')				//e不是'('
		{
			postexp[i++] = e;		//將e存放到postexp中
			Pop(Optr, e);		//出棧元素e
		}
		else					//e是'(時(shí)退出循環(huán)
			break;
	}
	Push(Optr, *exp);			//將'+'或'-'進(jìn)棧
	exp++;						//繼續(xù)掃描其他字符
	break;

• 其次就是【*】【/】，同樣，也是在棧不空時(shí)循環(huán)，獲取到棧頂元素，若是碰到相同的乘號(hào)或除號(hào)，則將它們放入postexp中，若是沒(méi)有，則跳出循環(huán)，直接將它們放入棧中即可

case '*':						//判定為'*'或'/'號(hào)
case '/':
	while (!StackEmpty(Optr))	//棧不空循環(huán)
	{
		GetTop(Optr, e);			//取棧頂元素e
		if (e == '*' || e == '/')	//將棧頂'*'或'/'運(yùn)算符出棧并存放到postexp中
		{
			postexp[i++] = e;		//將e存放到postexp中
			Pop(Optr, e);		//出棧元素e
		}
		else					//e為非'*'或'/'運(yùn)算符時(shí)退出循環(huán)
			break;
	}
	Push(Optr, *exp);			//將'*'或'/'進(jìn)棧
	exp++;						//繼續(xù)掃描其他字符
	break;

• 最后就是另外的數(shù)字情況的判斷，若為數(shù)字字符，直接將其放入postexp中即可，然后在每個(gè)數(shù)字后加一個(gè)空格來(lái)進(jìn)行標(biāo)識(shí)

default:				//處理數(shù)字字符
	while (*exp >= '0' && *exp <= '9') //判定為數(shù)字
	{
		postexp[i++] = *exp;
		exp++;
	}
	postexp[i++] = ' ';	//用空格標(biāo)識(shí)一個(gè)數(shù)值串結(jié)束

• 最后面的這段就是處理最后棧中還剩余的元素，將其依次出棧放入postexp即可，直到棧為空為止，最后別忘了postexp也是一個(gè)字符串，既然是字符串最后就要手動(dòng)加上’\0’，就是尾插法最后要的r - >next = NULL是一個(gè)道理

while (!StackEmpty(Optr))	//此時(shí)exp掃描完畢,棧不空時(shí)循環(huán)
{
	Pop(Optr, e);			//出棧元素e
	postexp[i++] = e;			//將e存放到postexp中
}
postexp[i] = '\0';			//給postexp表達(dá)式添加結(jié)束標(biāo)識(shí)
DestroyStack(Optr);			//銷(xiāo)毀棧

看完了上面的細(xì)致講解，難道你還想退出嗎，不想的話就繼續(xù)跟著我來(lái)吧??

?閉隱：如何對(duì)后綴表達(dá)式進(jìn)行求值？【???】

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式后，只是完成了我們的第一步，也就是有了一個(gè)模型了，接下去就要將其細(xì)心雕刻直至完美??

• 對(duì)后綴表達(dá)式的求值并不是很難，但是也需要涉及到堆棧FILO的原理，這需要你對(duì)Stack非常得熟悉
• 這里的順序棧數(shù)據(jù)結(jié)構(gòu)體的數(shù)據(jù)類(lèi)型要記得換一下，不可以用char了，前面我們是在遍歷字符，所以用char，但是這里是要去求值，但是數(shù)字可能會(huì)是小數(shù)，所以最好聲明成double類(lèi)型，這個(gè)不難，只需要改一下各個(gè)數(shù)據(jù)類(lèi)型即可

??運(yùn)算規(guī)則

首先一樣，我們要了解一下其運(yùn)算規(guī)則

• 后綴表達(dá)式求值的算法是遍歷后綴表達(dá)式，如果遇到運(yùn)算數(shù)，那么運(yùn)算數(shù)入棧
• 如果遇到運(yùn)算符，那么彈出棧里面兩個(gè)元素，先彈出的是右運(yùn)算數(shù)，后彈出的是左運(yùn)算數(shù)，計(jì)算運(yùn)算結(jié)果，然后將結(jié)果入棧。最后遍歷到后綴表達(dá)式末尾，當(dāng)結(jié)果只有一個(gè)元素時(shí)，就是答案

double compvalue(char* postexp)	//計(jì)算后綴表達(dá)式的值
{
	double d, a, b, c, e;
	SqStack1* Opnd;				//定義操作數(shù)棧
	InitStack1(Opnd);			//初始化操作數(shù)棧
	while (*postexp != '\0')		//postexp字符串未掃描完時(shí)循環(huán)
	{
		switch (*postexp)
		{
		case '+':				//判定為'+'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b + a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '-':				//判定為'-'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b - a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '*':				//判定為'*'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b * a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '/':				//判定為'/'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			if (a != 0)
			{
				c = b / a;			//計(jì)算c
				Push1(Opnd, c);	//將計(jì)算結(jié)果c進(jìn)棧
				break;
			}
			else
			{
				printf("\n\t除零錯(cuò)誤!\n");
				exit(0);		//異常退出
			}
			break;
		default:				//處理數(shù)字字符
			d = 0;				//將連續(xù)的數(shù)字字符轉(zhuǎn)換成對(duì)應(yīng)的數(shù)值存放到d中
			while (*postexp >= '0' && *postexp <= '9')   //判定為數(shù)字字符
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			Push1(Opnd, d);		//將數(shù)值d進(jìn)棧

			break;
		}
		postexp++;				//繼續(xù)處理其他字符
	}
	GetTop1(Opnd, e);			//取棧頂元素e
	DestroyStack1(Opnd);		//銷(xiāo)毀棧		
	return e;					//返回e
}

??關(guān)鍵代碼講解

• 這里主要是講講解一下如何去運(yùn)算，看到【default】分支，當(dāng)后綴表達(dá)式碰到數(shù)字字符的時(shí)候，這里需要將其轉(zhuǎn)換為數(shù)字，也就是 - ‘0’，因?yàn)椤?’的ASCLL碼值為48。假設(shè)一個(gè)數(shù)為1,1的ASCLL碼值為49，那么49-48也就是1
• 主要還是來(lái)解釋一下為什么d 要乘10，大家可以看到，這是一個(gè)while循環(huán)，因?yàn)檫@是一個(gè)不斷在找數(shù)字的過(guò)程，若是在遍歷到數(shù)字字符后又遍歷到了一個(gè)，那要如何運(yùn)算呢，*10就代表著上一個(gè)數(shù)字要為十位，而當(dāng)前遍歷數(shù)字在轉(zhuǎn)換為數(shù)字后是為個(gè)位，將遍歷到的所有數(shù)字字符轉(zhuǎn)換后進(jìn)行一個(gè)相加，最后當(dāng)遍歷到的不是數(shù)字字符時(shí)，才將此相加完的數(shù)放入棧中，然后退出循環(huán)去處理下一個(gè)字符

??觀鏡：結(jié)果測(cè)試

??測(cè)試結(jié)果展示

首先，就是要在main函數(shù)中，傳入對(duì)應(yīng)的exp和postexp

• 尤其是對(duì)于這個(gè)exp，大家千萬(wàn)不要留空格，否則在中綴轉(zhuǎn)后綴的時(shí)候就會(huì)出現(xiàn)數(shù)組越界異常
• 也就是因?yàn)檫@幾個(gè)空格，我調(diào)試了一個(gè)下午??

char exp[] = "(56 - 20)/(4 + 2)";	//錯(cuò)誤?。?！
char exp[] = "(56-20)/(4+2)";		//正確！??！

char exp[] = "5+8*2+(3*9+6)*4";
char postexp[MaxSize];
trans(exp, postexp);

printf("中綴表達(dá)式為：%s\n", exp);
printf("后綴表達(dá)式為：%s\n", postexp);
printf("表達(dá)式的值為：%g\n", compvalue(postexp));

這就是最終的結(jié)果，看后綴表達(dá)式，和我們上面通過(guò)堆棧原理分析的完全吻合，大家算出來(lái)是這樣嗎??

??整體代碼展示

//求簡(jiǎn)單表達(dá)式的值
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
//---------------------------------------------------------
//--運(yùn)算符?；具\(yùn)算---------------------------------------
//---------------------------------------------------------
typedef struct
{
	char data[MaxSize];			//存放運(yùn)算符
	int top;					//棧頂指針
} SqStack;
void InitStack(SqStack*& s)		//初始化棧
{
	s = (SqStack*)malloc(sizeof(SqStack));
	s->top = -1;
}
void DestroyStack(SqStack*& s)	//銷(xiāo)毀棧
{
	free(s);
}
bool StackEmpty(SqStack* s)		//判斷棧是否為空
{
	return(s->top == -1);
}
bool Push(SqStack*& s, char e)	//進(jìn)棧元素e
{
	if (s->top == MaxSize - 1)
		return false;
	s->top++;
	s->data[s->top] = e;
	return true;
}
bool Pop(SqStack*& s, char& e)	//出棧元素e
{
	if (s->top == -1)
		return false;
	e = s->data[s->top];
	s->top--;
	return true;
}
bool GetTop(SqStack* s, char& e)	//取棧頂元素e
{
	if (s->top == -1)
		return false;
	e = s->data[s->top];
	return true;
}
//---------------------------------------------------------

void trans(char* exp, char postexp[])	//將算術(shù)表達(dá)式exp轉(zhuǎn)換成后綴表達(dá)式postexp
{
	char e;
	SqStack* Optr;						//定義運(yùn)算符棧
	InitStack(Optr);					//初始化運(yùn)算符棧
	int i = 0;							//i作為postexp的下標(biāo)
	while (*exp != '\0')					//exp表達(dá)式未掃描完時(shí)循環(huán)
	{
		switch (*exp)
		{
		case '(':						//判定為左括號(hào)
			Push(Optr, '(');				//左括號(hào)進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		case ')':						//判定為右括號(hào)
			Pop(Optr, e);				//出棧元素e
			while (e != '(')				//不為'('時(shí)循環(huán)
			{
				postexp[i++] = e;			//將e存放到postexp中
				Pop(Optr, e);			//繼續(xù)出棧元素e
			}
			exp++;						//繼續(xù)掃描其他字符
			break;
		case '+':						//判定為加或減號(hào)
		case '-':
			while (!StackEmpty(Optr))	//棧不空循環(huán)
			{
				GetTop(Optr, e);			//取棧頂元素e
				if (e != '(')				//e不是'('
				{
					postexp[i++] = e;		//將e存放到postexp中
					Pop(Optr, e);		//出棧元素e
				}
				else					//e是'(時(shí)退出循環(huán)
					break;
			}
			Push(Optr, *exp);			//將'+'或'-'進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		case '*':						//判定為'*'或'/'號(hào)
		case '/':
			while (!StackEmpty(Optr))	//棧不空循環(huán)
			{
				GetTop(Optr, e);			//取棧頂元素e
				if (e == '*' || e == '/')	//將棧頂'*'或'/'運(yùn)算符出棧并存放到postexp中
				{
					postexp[i++] = e;		//將e存放到postexp中
					Pop(Optr, e);		//出棧元素e
				}
				else					//e為非'*'或'/'運(yùn)算符時(shí)退出循環(huán)
					break;
			}
			Push(Optr, *exp);			//將'*'或'/'進(jìn)棧
			exp++;						//繼續(xù)掃描其他字符
			break;
		default:				//處理數(shù)字字符
			while (*exp >= '0' && *exp <= '9') //判定為數(shù)字
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = ' ';	//用空格標(biāo)識(shí)一個(gè)數(shù)值串結(jié)束
		}
	}
	while (!StackEmpty(Optr))	//此時(shí)exp掃描完畢,棧不空時(shí)循環(huán)
	{
		Pop(Optr, e);			//出棧元素e
		postexp[i++] = e;			//將e存放到postexp中
	}
	postexp[i] = '\0';			//給postexp表達(dá)式添加結(jié)束標(biāo)識(shí)
	DestroyStack(Optr);			//銷(xiāo)毀棧		
}
//---------------------------------------------------------
//--操作數(shù)?；具\(yùn)算---------------------------------------
//---------------------------------------------------------
typedef struct
{
	double data[MaxSize];			//存放數(shù)值
	int top;						//棧頂指針
} SqStack1;
void InitStack1(SqStack1*& s)		//初始化棧
{
	s = (SqStack1*)malloc(sizeof(SqStack1));
	s->top = -1;
}
void DestroyStack1(SqStack1*& s)	//銷(xiāo)毀棧
{
	free(s);
}
bool StackEmpty1(SqStack1* s)		//判斷棧是否為空
{
	return(s->top == -1);
}
bool Push1(SqStack1*& s, double e)	//進(jìn)棧元素e
{
	if (s->top == MaxSize - 1)
		return false;
	s->top++;
	s->data[s->top] = e;
	return true;
}
bool Pop1(SqStack1*& s, double& e)	//出棧元素e
{
	if (s->top == -1)
		return false;
	e = s->data[s->top];
	s->top--;
	return true;
}
bool GetTop1(SqStack1* s, double& e)	//取棧頂元素e
{
	if (s->top == -1)
		return false;
	e = s->data[s->top];
	return true;
}
//---------------------------------------------------------

double compvalue(char* postexp)	//計(jì)算后綴表達(dá)式的值
{
	double d, a, b, c, e;
	SqStack1* Opnd;				//定義操作數(shù)棧
	InitStack1(Opnd);			//初始化操作數(shù)棧
	while (*postexp != '\0')		//postexp字符串未掃描完時(shí)循環(huán)
	{
		switch (*postexp)
		{
		case '+':				//判定為'+'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b + a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '-':				//判定為'-'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b - a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '*':				//判定為'*'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			c = b * a;				//計(jì)算c
			Push1(Opnd, c);		//將計(jì)算結(jié)果c進(jìn)棧
			break;
		case '/':				//判定為'/'號(hào)
			Pop1(Opnd, a);		//出棧元素a
			Pop1(Opnd, b);		//出棧元素b
			if (a != 0)
			{
				c = b / a;			//計(jì)算c
				Push1(Opnd, c);	//將計(jì)算結(jié)果c進(jìn)棧
				break;
			}
			else
			{
				printf("\n\t除零錯(cuò)誤!\n");
				exit(0);		//異常退出
			}
			break;
		default:				//處理數(shù)字字符
			d = 0;				//將連續(xù)的數(shù)字字符轉(zhuǎn)換成對(duì)應(yīng)的數(shù)值存放到d中
			while (*postexp >= '0' && *postexp <= '9')   //判定為數(shù)字字符
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			Push1(Opnd, d);		//將數(shù)值d進(jìn)棧

			break;
		}
		postexp++;				//繼續(xù)處理其他字符
	}
	GetTop1(Opnd, e);			//取棧頂元素e
	DestroyStack1(Opnd);		//銷(xiāo)毀棧		
	return e;					//返回e
}
void test()
{
	char exp[] = "5+8*2+(3*9+6)*4";
	char postexp[MaxSize];
	trans(exp, postexp);

	printf("中綴表達(dá)式為：%s\n", exp);
	printf("后綴表達(dá)式為：%s\n", postexp);
	printf("表達(dá)式的值為：%g\n", compvalue(postexp));
	
}

int main(void)
{
	test();
	return 0;
}

??開(kāi)戰(zhàn)：實(shí)戰(zhàn)演練【LeetCode習(xí)題深入】

明白了如何將一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并且清楚了如何求值。接下來(lái)讓我們到力扣上去找道題去練練手吧

原題傳送門(mén)——逆波蘭表達(dá)式求值

??題目描述

根據(jù) 逆波蘭表示法，求表達(dá)式的值。

有效的算符包括 +、-、*、/ 。每個(gè)運(yùn)算對(duì)象可以是整數(shù)，也可以是另一個(gè)逆波蘭表達(dá)式。

注意 兩個(gè)整數(shù)之間的除法只保留整數(shù)部分。

可以保證給定的逆波蘭表達(dá)式總是有效的。換句話說(shuō)，表達(dá)式總會(huì)得出有效數(shù)值且不存在除數(shù)為 0 的情況。

示例 1：

輸入：tokens = [“2”,“1”,“+”,“3”,“*”]
輸出：9
解釋?zhuān)涸撍闶睫D(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9

示例 2：

輸入：tokens = [“4”,“13”,“5”,“/”,“+”]
輸出：6
解釋?zhuān)涸撍闶睫D(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：(4 + (13 / 5)) = 6

示例 3：

輸入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
輸出：22
解釋?zhuān)涸撍闶睫D(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

??思路分析

• 首先對(duì)于逆波蘭表達(dá)式，它其實(shí)和二叉樹(shù)的后續(xù)遍歷挺像的， 大家可以把運(yùn)算符作為中間節(jié)點(diǎn)，按照后序遍歷的規(guī)則畫(huà)出一個(gè)二叉樹(shù)。
• 我們已經(jīng)了解了它的運(yùn)算規(guī)則，題目已經(jīng)是一個(gè)后綴表達(dá)式，所以我們不需要進(jìn)行繁瑣的轉(zhuǎn)換，只要對(duì)給出的字符串進(jìn)行一個(gè)遍歷，看它是數(shù)字還是加減乘除運(yùn)算符即可

??動(dòng)畫(huà)展示

溫馨提示，微信手機(jī)端看不到

??整體代碼展示

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i = 0;i < tokens.size(); ++i)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int num1 = st.top();    st.pop();
                int num2 = st.top();    st.pop();

                if(tokens[i] == "+")    st.push(num2 + num1);
                if(tokens[i] == "-")    st.push(num2 - num1);
                if(tokens[i] == "*")    st.push((long long)num2 * num1);
                if(tokens[i] == "/")    st.push(num2 / num1);
            }
            else
            {
                //若為數(shù)字字符，則將其轉(zhuǎn)換為數(shù)字，方便后續(xù)運(yùn)算
                st.push(stoi(tokens[i]));   
            }
        }
        int ret = st.top();
        st.pop();
        return ret;
    }
};

??重點(diǎn)講解

• 代碼很簡(jiǎn)單，就是去遍歷給出的這個(gè)字符串，判斷其為加減乘數(shù)四個(gè)運(yùn)算符，是的話就將棧中的頭兩個(gè)元素出棧，進(jìn)行一個(gè)四則運(yùn)算，但是這里要注意的是因?yàn)檎故綟ILO，

• 你第一個(gè)進(jìn)棧的，也就是第二個(gè)出棧的才是第一個(gè)操作符

• 你第二個(gè)進(jìn)棧的，也就是你第一個(gè)出棧的是第二個(gè)操作符

• 這個(gè)邏輯一定要理清，否則會(huì)出現(xiàn)運(yùn)算問(wèn)題，可以看到這里的運(yùn)算num2都是在num1的前面

• 若不是四個(gè)運(yùn)算符，則將其轉(zhuǎn)換為數(shù)字進(jìn)棧即可，這里用到了一個(gè)比較偏僻的函數(shù)stoi（），它可以將一個(gè)字符轉(zhuǎn)換為數(shù)字形式，大家不清楚的可以去了解一下

??歸思：總結(jié)與提煉

OK，這就是我們今天要講解的內(nèi)容，有關(guān)數(shù)據(jù)結(jié)構(gòu)中堆棧應(yīng)用方面——后綴表達(dá)式，你學(xué)廢了嗎??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-426760.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) | 后綴表達(dá)式【深入剖析堆棧原理】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！