實例解析Java中綴表達式的實現

本篇文章為大家帶來了關於java的相關知識，其中主要介紹了關於中綴表達式是一個通用的算術或邏輯公式表示方法。中綴表達式不容易被電腦解析，但仍被許多程式語言使用，因為它符合人們的普遍用法。下面一起來看一下，希望對大家有幫助。

推薦學習：《java影片教學》

1.概念

什麼是中綴表達式，什麼是後綴表達式?

從小學開始學習的四則運算，例如：3 (5*(2 3) 7) 類似這種表達式就是中綴表達式。中綴表達式人腦很容易理解，各個算符的優先級，人腦也很容易判斷，先算括弧裡的，再算*，再算，-

但是這種表達式很不利於計算機計算，透過某種方式把前綴表達式轉換為後綴表達式方便計算機進行計算，如3 (5*(2 3) 7)的後綴表達式就是3,5,2,3, ,*, 7, , 。這個表達式計算機很容易計算，為什麼容易計算，透過演算法流程2，就會一個深入的理解。

2.演算法流程

如何把中綴表達式轉換成後綴表達式?比如說3 (5*(2 3) 7)的轉成後綴表達式的流程如何？

運算子優先權:

• ,- 小於*，/
• 等於-
• * 等於/

左括號和右括號作為特殊運算子特殊處理。 (碰到'('不用判斷優先權直接入運算子棧，碰到')',也不用判斷優先權,直接出運算子棧)

大致演算法掌握以下幾個流程：

準備兩個棧，一個是數字棧A，一個是操作符棧( ,-,*,/(,))B等

1.0 對於數字棧A，遇到數字直接入棧A。

2.0 對於運算子堆疊B，分成幾種情況

2.1 碰到'('運算子直接入堆疊

2.2 碰到')'運算符，不停的把操作符棧B出棧，直到遇到')'。 （把'('到')'之間的彈出的運算子依序入堆疊A）

2.3 碰到' ,-,* /'比較當前元素（假設當前元素current）和B棧棧頂的運算子(假設棧頂元素是top)的優先權.

2.3.1 如果top >= current, B堆疊出棧且循環比較，直到top < current退出循環，並且把current入棧

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

3.0 掃描完整個字串，如果B棧中還有操作符，依序出棧入A

依照上述演算法示範3 (5*(2 3) 7)的流程：

1，碰到3，3入A堆疊[3,]
2 ，碰到，入B棧  [ ,]
3，碰到(，入B棧  [ ,(]
4，碰到5，入A棧  [3,5]
5，碰到*，*的優先權大於(,入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 ，碰到, 的優先權小於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, 掃描完整個字串，判斷B是否為空，不為空把B棧的元素彈出，入A。目前不為空，所以最終A棧的元素為A:[3,5,2,3, ,*,7, , ]

##所以最終A的後綴表達式是3,5,2,3, ,*,7, ,

計算機拿到這個會怎麼計算呢？流程如下：

碰到數字直接入棧
• 碰到操作符，直接彈出兩個棧頂元素，透過運算元計算，把結果壓入堆疊

透過步驟1，2循環計算，最後堆疊裡只會有一個元素，這個就是表達式的結果。

我們來演練一下：

1,碰到數字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]

透過上面可以得知，計算機很容易計算，從左到右就能把結果得出。

3 程式碼實作

mid2post 求後綴表達式

calcPostExp 拿到後綴表達式求值

cmpPriority 優先權比較

//优先级
bool cmpPriority(char top, char cur)//比较当前字符与栈顶字符的优先级，若栈顶高，返回true
{
	if ((top == '+' || top == '-') && (cur == '+' || cur == '-'))
		return true;
	if ((top == '*' || top == '/') && (cur == '+' || cur == '-' || top == '*' || top == '/'))
		return true;
	if (cur == ')')
		return true;
	return false;
}

求後綴表達式求值

vector<string> mid2post(string &str)
{

	vector<string>vstr;
	stack<char>cstack;
	for (int i = 0;i<str.size();++i)//扫描字符串
	{
		string temp = "";
		if (str[i] >= &#39;0&#39; && str[i] <= &#39;9&#39;)//若是数字
		{
			temp += str[i];
			while (i + 1<str.size() && str[i + 1] >= &#39;0&#39; && str[i + 1] <= &#39;9&#39;)
			{
				temp += str[i + 1];//若是连续数字
				++i;
			}
			vstr.push_back(temp);
		}
		else if (cstack.empty() || str[i] == &#39;(&#39;)//若栈空或者字符为&#39;(&#39;
			cstack.push(str[i]);
		else if (cmpPriority(cstack.top(), str[i]))//若栈顶元素优先级较高，栈顶元素出栈
		{
			if (str[i] == &#39;)&#39;)//若当前字符是右括号，栈中元素出栈，入字符串数组中，直到遇到&#39;(&#39;
			{
				while (!cstack.empty() && cstack.top() != &#39;(&#39;)
				{
					temp += cstack.top();
					cstack.pop();
					vstr.push_back(temp);
					temp = "";
				}
				cstack.pop();
			}
			else//栈中优先级高的元素出栈，入字符串数组，直到优先级低于当前字符
			{
				while (!cstack.empty() && cmpPriority(cstack.top(), str[i]))
				{
					temp += cstack.top();
					cstack.pop();
					vstr.push_back(temp);
					temp = "";
				}
				cstack.push(str[i]);
			}
		}
		else//当前字符优先级高于栈顶元素，直接入栈
			cstack.push(str[i]);
	}
	while (!cstack.empty())//栈中还存在运算符时，出栈，存入字符串数组
	{
		string temp = "";
		temp += cstack.top();
		cstack.pop();
		vstr.push_back(temp);
	}
	return vstr;
}

對後綴表達式進行求值，主要是根據運算子取出兩個

int calcPostExp(vector<string> & vstr)//对后缀表达式进行求值，主要是根据运算符取出两个操作数进行运算
{
	int num, op1, op2;
	stack<int>opstack;
	for (int i = 0;i<vstr.size();++i)
	{
		string temp = vstr[i];
		if (temp[0] >= &#39;0&#39; && temp[0] <= &#39;9&#39;)//如果当前字符串是数字，利用字符串流转化为int型
		{
			stringstream ss;
			ss << temp;
			ss >> num;
			opstack.push(num);
		}
		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);
		}
		else if (vstr[i] == "/")
		{
			op2 = opstack.top();
			opstack.pop();
			op1 = opstack.top();
			opstack.pop();
			opstack.push(op1 / op2);
		}
	}
	return opstack.top();//最终的栈顶元素就是求解的结果
}

推薦學習：《

java影片教學》

以上是實例解析Java中綴表達式的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！