站長資訊網本篇文章給大家帶來了關于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] >= '0' && str[i] <= '9')//若是數字 { temp += str[i]; while (i + 1<str.size() && str[i + 1] >= '0' && str[i + 1] <= '9') { temp += str[i + 1];//若是連續數字 ++i; } vstr.push_back(temp); } else if (cstack.empty() || str[i] == '(')//若棧空或者字符為'(' cstack.push(str[i]); else if (cmpPriority(cstack.top(), str[i]))//若棧頂元素優先級較高，棧頂元素出棧 { if (str[i] == ')')//若當前字符是右括號，棧中元素出棧，入字符串數組中，直到遇到'(' { while (!cstack.empty() && cstack.top() != '(') { 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] >= '0' && temp[0] <= '9')//如果當前字符串是數字，利用字符串流轉化為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視頻教程》
