本篇文章給大家?guī)砹岁P(guān)于java的相關(guān)知識，其中主要介紹了關(guān)于中綴表達(dá)式是一個(gè)通用的算術(shù)或邏輯公式表示方法。中綴表達(dá)式不容易被計(jì)算機(jī)解析，但仍被許多程序語言使用，因?yàn)樗先藗兊钠毡橛梅?。下面一起來看一下，希望對大家有幫助?/p>

推薦學(xué)習(xí)：《java視頻教程》

1.概念

什么是中綴表達(dá)式，什么是后綴表達(dá)式?

從小學(xué)開始學(xué)習(xí)的四則運(yùn)算，例如：3+(5*(2+3)+7) 類似這種表達(dá)式就是中綴表達(dá)式。中綴表達(dá)式人腦很容易理解，各個(gè)算符的優(yōu)先級，人腦也很容易判斷，先算括弧里的，再算*，再算+，-

但是這種表達(dá)式很不利于計(jì)算機(jī)計(jì)算，通過某種方式把前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式方便計(jì)算機(jī)進(jìn)行計(jì)算，如3+(5*(2+3)+7)的后綴表達(dá)式就是3,5,2,3,+,*,7,+, +。這個(gè)表達(dá)式計(jì)算機(jī)很容易計(jì)算，為什么容易計(jì)算，通過算法流程2，就會(huì)一個(gè)深入的理解。

2.算法流程

如何把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式?比如說3+(5*(2+3)+7)的轉(zhuǎn)成后綴表達(dá)式的流程如何？

操作符優(yōu)先級:

• +,- 小于*，/
• + 等于 –
• * 等于 /

左括號和右括號作為特殊操作符特殊處理。(碰到’(’不用判斷優(yōu)先級直接入操作符棧，碰到’)’,也不用判斷優(yōu)先級,直接出操作符棧)

大致算法掌握以下幾個(gè)流程：

準(zhǔn)備兩個(gè)棧，一個(gè)是數(shù)字棧A，一個(gè)是操作符棧(+,-,*,/(,))B等

1.0 對于數(shù)字棧A，遇到數(shù)字直接入棧A。

2.0 對于操作符棧B，分幾種情況

2.1 碰到 ‘(‘操作符直接入棧

2.2 碰到 ‘)’操作符，不停的把操作符棧B出棧，直到遇到’)’。（把’(’到’)’之間的彈出的操作符依次入棧A）

2.3 碰到’+,-,* /’比較當(dāng)前元素（假設(shè)當(dāng)前元素current）和B棧棧頂?shù)牟僮鞣?假設(shè)棧頂元素是top)的優(yōu)先級.

2.3.1 如果top >= current, B棧出棧且循環(huán)比較，直到top < current退出循環(huán)，且把 current入棧

2.3.2 如果top < current, 直接把current入B棧

3.0 掃描完整個(gè)字符串，如果B棧中還有操作符，依次出棧入A

按照上面算法演示3+(5*(2+3)+7)的流程：

1，碰到3，3入A棧 [3,]
2，碰到+，入B棧 [+,]
3，碰到(，入B棧 [+,(]
4，碰到5，入A棧 [3,5]
5，碰到*，*的優(yōu)先級大于 (,入B棧[ +,(,*]
6，碰到(,入B棧[ +,(,*,(]
7，碰到2，入A棧 [3,5,2]
8，碰到+,入B棧[ +,(,*,(,+]
9，碰到3，入A棧 [3,5,2,3]
10，碰到),彈出B棧，直接到 ‘(‘，把彈出的操作符入A棧。B:[ +,(,*] A:[3,5,2,3,+]
11，碰到+, +的優(yōu)先級小于B的棧頂元素 *，所以*從B出棧，入A,并把+入B。B:[ +,(,+] A:[3,5,2,3,+,*]
12，碰到7，入A棧 [3,5,2,3,+,*,7]
13，碰到),彈出B棧，直接到 ‘(‘，把彈出的操作符入A棧。B:[ +] A:[3,5,2,3,+,*,7,+]
14, 掃描完整個(gè)字符串，判斷B是否為空，不為空把B棧的元素彈出，入A。當(dāng)前不為空，所以最終A棧的元素為 A:[3,5,2,3,+,*,7,+, +]

所以最終A的后綴表達(dá)式是3,5,2,3,+,*,7,+, +

計(jì)算機(jī)拿到這個(gè)會(huì)怎么計(jì)算呢？流程如下：

• 碰到數(shù)字直接入棧
• 碰到操作符，直接彈出兩個(gè)棧頂元素，通過操作符計(jì)算，把結(jié)果壓入棧

通過步驟1，2循環(huán)計(jì)算，最終棧里只會(huì)有一個(gè)元素，這個(gè)就是表達(dá)式的結(jié)果。

我們來演練一下：

1,碰到數(shù)字3,5,2,3直接入棧A[3,5,2,3]
2,碰到+，彈出棧頂2，3，相加得5 入棧A[3,5,5]
3,碰到*，彈出棧頂5，5，相乘得25 入棧A[3,25]
4,碰到7，直接入棧A[3,25,7]
5,碰到+，彈出棧頂25，7，相加得32 入棧A[3,32]
6,碰到+，彈出棧頂3，32，相加得35 入棧A[35]

通過上面可以得知，計(jì)算機(jī)很容易計(jì)算，從左掃描到右就能把結(jié)果得出。

3 代碼實(shí)現(xiàn)

mid2post 求后綴表達(dá)式

calcPostExp 拿到后綴表達(dá)式求值

cmpPriority 優(yōu)先級比較

//優(yōu)先級 bool cmpPriority(char top, char cur)//比較當(dāng)前字符與棧頂字符的優(yōu)先級，若棧頂高，返回true { 	if ((top == '+' || top == '-') && (cur == '+' || cur == '-')) 		return true; 	if ((top == '*' || top == '/') && (cur == '+' || cur == '-' || top == '*' || top == '/')) 		return true; 	if (cur == ')') 		return true; 	return false; }

求后綴表達(dá)式求值

vector<string> mid2post(string &str) {  	vector<string>vstr; 	stack<char>cstack; 	for (int i = 0;i<str.size();++i)//掃描字符串 	{ 		string temp = ""; 		if (str[i] >= '0' && str[i] <= '9')//若是數(shù)字 		{ 			temp += str[i]; 			while (i + 1<str.size() && str[i + 1] >= '0' && str[i + 1] <= '9') 			{ 				temp += str[i + 1];//若是連續(xù)數(shù)字 				++i; 			} 			vstr.push_back(temp); 		} 		else if (cstack.empty() || str[i] == '(')//若?？栈蛘咦址麨?#39;(' 			cstack.push(str[i]); 		else if (cmpPriority(cstack.top(), str[i]))//若棧頂元素優(yōu)先級較高，棧頂元素出棧 		{ 			if (str[i] == ')')//若當(dāng)前字符是右括號，棧中元素出棧，入字符串?dāng)?shù)組中，直到遇到'(' 			{ 				while (!cstack.empty() && cstack.top() != '(') 				{ 					temp += cstack.top(); 					cstack.pop(); 					vstr.push_back(temp); 					temp = ""; 				} 				cstack.pop(); 			} 			else//棧中優(yōu)先級高的元素出棧，入字符串?dāng)?shù)組，直到優(yōu)先級低于當(dāng)前字符 			{ 				while (!cstack.empty() && cmpPriority(cstack.top(), str[i])) 				{ 					temp += cstack.top(); 					cstack.pop(); 					vstr.push_back(temp); 					temp = ""; 				} 				cstack.push(str[i]); 			} 		} 		else//當(dāng)前字符優(yōu)先級高于棧頂元素，直接入棧 			cstack.push(str[i]); 	} 	while (!cstack.empty())//棧中還存在運(yùn)算符時(shí)，出棧，存入字符串?dāng)?shù)組 	{ 		string temp = ""; 		temp += cstack.top(); 		cstack.pop(); 		vstr.push_back(temp); 	} 	return vstr; }

對后綴表達(dá)式進(jìn)行求值，主要是根據(jù)運(yùn)算符取出兩

int calcPostExp(vector<string> & vstr)//對后綴表達(dá)式進(jìn)行求值，主要是根據(jù)運(yùn)算符取出兩個(gè)操作數(shù)進(jìn)行運(yùn)算 { 	int num, op1, op2; 	stack<int>opstack; 	for (int i = 0;i<vstr.size();++i) 	{ 		string temp = vstr[i]; 		if (temp[0] >= '0' && temp[0] <= '9')//如果當(dāng)前字符串是數(shù)字，利用字符串流轉(zhuǎn)化為int型 		{ 			stringstream ss; 			ss << temp; 			ss >> num; 			opstack.push(num); 		} 		else if (vstr[i] == "+")//若是操作符，取出兩個(gè)操作數(shù)，進(jìn)行運(yùn)算，并將結(jié)果存入 		{ 			op2 = opstack.top(); 			opstack.pop(); 			op1 = opstack.top(); 			opstack.pop(); 			opstack.push(op1 + op2); 		} 		else if (vstr[i] == "-") 		{ 			op2 = opstack.top(); 			opstack.pop(); 			op1 = opstack.top(); 			opstack.pop(); 			opstack.push(op1 - op2); 		} 		else if (vstr[i] == "*") 		{ 			op2 = opstack.top(); 			opstack.pop(); 			op1 = opstack.top(); 			opstack.pop(); 			opstack.push(op1*op2); 		} 		else if (vstr[i] == "/") 		{ 			op2 = opstack.top(); 			opstack.pop(); 			op1 = opstack.top(); 			opstack.pop(); 			opstack.push(op1 / op2); 		} 	} 	return opstack.top();//最終的棧頂元素就是求解的結(jié)果 }

推薦學(xué)習(xí)：《java視頻教程》