中綴表達式轉為後綴表達式（逆波蘭式）求值
- 2020 年 5 月 12 日
- 筆記
- 數據結構（Java）
一、中綴與後綴表達式的介紹
1.中綴表達式
中綴表達式是一個通用的算術或邏輯公式表示方法。中綴表達式（或中綴記法）是一個通用的算術或邏輯公式表示方法， 操作符是以中綴形式處於操作數的中間（例：3 + 4），中綴表達式是人們常用的算術表示方法。
與前綴表達式（例：+ 3 4）或後綴表達式（例：3 4 +）相比，中綴表達式不容易被電腦解析，但仍被許多程式語言使用，因為它符合人們的普遍用法。
與前綴或後綴記法不同的是，中綴記法中括弧是必需的。計算過程中必須用括弧將操作符和對應的操作數括起來，用於指示運算的次序。
例：
（1）8+4-6*2用後綴表達式表示為：
8 4+6 2*-
（2）2*(3+5)+7/1-4用後綴表達式表示為：
235+*71/+4-
2.後綴表達式（逆波蘭式）
逆波蘭式（Reverse Polish notation，RPN，或逆波蘭記法），也叫後綴表達式（將運算符寫在操作數之後）
定義
一個表達式E的後綴形式可以如下定義：
（2）如果E是E1 op E2形式的表達式，這裡op是任何二元操作符，則E的後綴式為E1’E2′ op，這裡E1’和E2’分別為E1和E2的後綴式。
（3)如果E是（E1）形式的表達式，則E1的後綴式就是E的後綴式。
用逆波蘭式計算表達式結果的方法為：
- 新建一個表達式
- 判斷當前字元
- 如果當前字元為變數或者為數字，則壓棧
- 如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧
- 最後當表達式掃描完後，棧里的就是結果。
二、待解決問題與解決思路
1.中綴表達式轉化為後綴表達式
- 初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
- 從左至右掃描中綴表達式；
- 遇到操作數時，將其壓s2
- 遇到運算符時，比較其與s1棧頂運算符的優先順序
- （1）如果s1為空，或棧頂運算符為左括弧「(」，則直接將此運算符入棧；
- （2）否則，若優先順序比棧頂運算符的高，也將運算符壓入s1；
- （3）否則，將s1棧頂的運算符彈出並壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；
- 遇到括弧時：
- （1）如果是左括弧「(」，則直接壓入s1
- （2）如果是右括弧「)」，則依次彈出s1棧頂的運算符，並壓入s2，直到遇到左括弧為止，此時將這一對括弧丟棄
- .重複步驟2至5，直到表達式的最右邊
- 將s1中剩餘的運算符依次彈出並壓入s2
- 依次彈出s2中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式
2.後綴表達式進行表達式求值
- 從左到右掃描表達式的字元。
- 對當前字元進行判斷
- (1)如果當前字元為運算符，則直接從將棧頂元素和次棧頂元素彈出，與當前運算符進行運算，將結果壓入棧中。
- (2)若當前字元為數字，直接壓入棧中。
- 循環2.1，2.2直到表達式掃描完畢，最後棧中的數字就是所要的結果。
三、程式碼實現
/**
* @author ymy
* @date 2020/5/12
*/
public class PolandNotation {
public static void main(String[] args) {
PolandNotation calculate = new PolandNotation();
// System.out.println(calculate.calculateSuffixExpression("30 4 + 5 * 6 -"));
String infix ="1+((2+3)*4)-5";
List<String> list = calculate.toInfixExpressionList(infix);
List<String> suffix= calculate.toSuffixExpression(list);
System.out.print("後綴表達式為：");
for (String s : suffix) {
System.out.print(s);
}
}
/**
* @param expressionStr 3 4 + 5 × 6 -
* @return 計算結果
*/
public int calculateSuffixExpression(String expressionStr) {
int res = 0;
List<String> expression = getListString(expressionStr);
Stack<Integer> stack = new Stack();
int num1;
int num2;
String operator = "";
for (int i = 0; i < expression.size(); i++) {
if (isOperaor(expression.get(i))) {
num1 = stack.pop();
num2 = stack.pop();
operator = expression.get(i);
res = calculate(num1, num2, operator);
stack.push(res);
} else {
stack.push(Integer.parseInt(expression.get(i)));
}
}
return res;
}
public int calculate(int num1, int num2, String operator) {
int res = 0;
switch (operator) {
case "+":
res = num1 + num2;
break;
case "-":
res = num2 - num1;
break;
case "*":
res = num1 * num2;
break;
case "/":
res = num2 / num1;
break;
}
return res;
}
public boolean isOperaor(String str) {
return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
}
public int getPriority(String oper){
if (oper.equals("+")||oper.equals("-"))
return 0;
if (oper.equals("*")||oper.equals("/"))
return 1;
return -1;
}
/**
* 將後綴表達式用list保存
*
* @param suffixExpression
* @return
*/
public List<String> getListString(String suffixExpression) {
ArrayList<String> list = new ArrayList();
String[] strings = suffixExpression.split(" ");
for (int i = 0; i < strings.length; i++) {
list.add(strings[i]);
}
return list;
}
/**
* @return 中綴表達式轉化為後綴表達式
* 1.初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
* 2.從左至右掃描中綴表達式；
* 3.遇到操作數時，將其壓s2；
* 4.遇到運算符時，比較其與s1棧頂運算符的優先順序：
* (1)如果s1為空，或棧頂運算符為左括弧「(」，則直接將此運算符入棧；
* (2)否則，若優先順序比棧頂運算符的高，也將運算符壓入s1；
* (3)否則，將s1棧頂的運算符彈出並壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；
* 5.遇到括弧時：
* (1) 如果是左括弧「(」，則直接壓入s1
* (2) 如果是右括弧「)」，則依次彈出s1棧頂的運算符，並壓入s2，直到遇到左括弧為止，此時將這一對括弧丟棄
* 6.重複步驟2至5，直到表達式的最右邊
* 7. 將s1中剩餘的運算符依次彈出並壓入s2
* 8.依次彈出s2中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式
*
*/
public List<String> toSuffixExpression(List<String> infix) {
LinkedList<String> suffix = new LinkedList<>();
Stack <String> operStack= new Stack();
Stack <String> resStack= new Stack();
String currentCh = "";
for (int i = 0; i <infix.size() ; i++) {
currentCh=infix.get(i);
if(!isOperaor(currentCh)&&!currentCh.equals("(")&&!currentCh.equals(")")){//如果是數字
resStack.push(currentCh);
}else if (isOperaor(currentCh)){//如果是運算符
//若此時運算符棧為空或者棧頂為(，則直接將運算符入棧
while (true){
if (operStack.isEmpty()||operStack.peek().equals("(")){
operStack.push(currentCh);
break;
}else if(getPriority(operStack.peek())<getPriority(currentCh)){
operStack.push(currentCh);
break;
}else {
resStack.push(operStack.pop());
}
}
}else if(currentCh.equals("(")) {
operStack.push(currentCh);
}else if(currentCh.equals(")")){
while (!operStack.peek().equals("(")){
resStack.push(operStack.pop());
}
operStack.pop();
continue;
}else{
throw new RuntimeException("表達式不規範");
}
}
while (!operStack.isEmpty()){
resStack.push(operStack.pop());
}
Stack<String> temp = new Stack<>();
while (!resStack.isEmpty()){
temp.push(resStack.pop());
}
while (!temp.isEmpty()){
suffix.add(temp.pop());
}
return suffix;
}
public List<String> toInfixExpressionList(String string) {
ArrayList<String> infix = new ArrayList<>();
int i = 0;//用來做掃描指針
String str = "";//用來拼接多位數字
char[] chars = string.trim().toCharArray();
System.out.println(chars);
for (int j = 0; j < chars.length; j++) {
if (isNumber(chars[j])) {
str += chars[j];
} else {
if (!str.equals("")){
infix.add(str);
str = "";
}
infix.add(chars[j] + "");
}
}
if (!str.equals("")) {
infix.add(str);
}
return infix;
}
public boolean isNumber(char ch) {
return !("0123456789".indexOf(ch + "") == -1);
}
}
四、運行結果
