參考鏈接
結合原文章募狂，做了一定修改蓝厌，增加Java源碼實現(xiàn)
1. 概述
對于四則運算表達式的計算顿仇，是輸入數(shù)據(jù)結構中棧的應用淘正，即重點是中綴表達式轉換為后綴表達式
2. 后綴表達式計算
- 為了解釋后綴表達式的好處摆马，我們先來看看，計算機是如何計算后綴表達式的
- 后綴表達式實例
9 3 1 - 3 * + 10 2 / + - 計算規(guī)則：從左到右遍歷表達式的每個數(shù)字和符號鸿吆，遇到數(shù)字就進棧今膊，遇到是符號，就將處于棧頂?shù)膬蓚€數(shù)字出棧伞剑，進行計算，然后計算結果進棧市埋，一直到最終獲得結果黎泣。
-
計算過程：
imageimage
image
image
3. 中綴表達式轉后綴表達式
我們把平時標準的四則運算表達式比如
9+(3-1)*3+10/2叫做中綴表達式。
中綴表達式：9+(3-1)*3+10/2轉換后綴表達式9 3 1 - 3 * + 10 2 / +
- 轉換規(guī)則：
- 當當前字符為
數(shù)字時缤谎，直接輸出抒倚； - 當當前字符為
(時，將其壓棧坷澡； - 當當前字符為
)時托呕，則彈出堆棧中最上的(之前的所有運算符并輸出，然后刪除堆棧中的(频敛； - 當當前字符為運算符時项郊，則依次彈出堆棧中優(yōu)先級
大于等于當前運算符的(到”(“之前為止)，輸出斟赚，再將當前運算符壓棧着降；
最后彈出所有棧中的內(nèi)容輸出
-
轉換過程
image
image
image
image
image
4. 源代碼實現(xiàn)
package data_structure;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* 棧的應用
* https://blog.csdn.net/u011857433/article/details/79993385
* 四則運算表達式求職，中綴表達式與后綴表達式轉換
*/
public class ReversePoland {
public static void main(String[] args) {
// Calculation1("9 3 1 - 3 * + 10 2 / +");
System.out.println(Calculation2("9 + ( 3 - 1 ) * 3 + 10 / 2"));
}
/**
* 計算后綴表達式
* @param inputString 9 3 1 - 3 * + 10 2 / + 以空格分隔
*/
public static int Calculation1(String inputString){
String[] input = inputString.split(" ");
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < input.length; i++) {
String s = input[i];
if (isNumber(s)) //如果是數(shù)字拗军，則入棧
stack.push(Integer.valueOf(s));
else {
//遇到運算符任洞，則從棧中彈出兩個數(shù)字，進行運算
int n1 = stack.pop();
int n2 = stack.pop();
int res = 0;
switch (s){
case "+":res = n1 + n2;break;
case "-":res = n2 - n1;break;
case "*":res = n1 * n2;break;
case "/":res = n2 / n1;break;
}
stack.push(res);
}
}
return stack.pop();
}
/**
* 將中綴表達式轉化為后綴表達式
* @param string 9 + ( 3 - 1 ) * 3 + 10 / 2
* @return
*/
public static String Calculation2(String string){
Stack<String> stack = new Stack();
String[] chars = string.split(" ");
String res = "";
for (int i = 0; i < chars.length; i++) {
String s = String.valueOf(chars[i]);
if (isNumber(s)){
if (res.length()==0)
res += s;
else
res += " "+s;
}else {
if (s.equals("(")){
stack.push(s);
}else {
if (s.equals(")")){
String t = "";
String s1 = "";
while (!(t = stack.pop()).equals("(")){
s1 += " "+t;
}
res += s1;
}else {
int priority = getPriority(s);
String s1 = "";
boolean flag = false;
while (!stack.empty()){
flag = false;
s1 = stack.pop();
if (s1.equals("(")){
// stack.push("(");
break;
}
if (getPriority(s1) >= priority){
res += " " + s1;
flag = true;
}
}
if (!s1.equals("") && !flag)
stack.push(s1);
stack.push(s);
}
}
}
}
while (!stack.empty()){
res += " " + stack.pop();
}
return res;
}
//獲取運算符的優(yōu)先級
public static int getPriority(String s){
Map<String,Integer> map = new HashMap<>();
map.put("+",0);
map.put("-",0);
map.put("*",1);
map.put("/",1);
map.put("(",2);
map.put(")",2);
return map.get(s);
}
public static boolean isNumber(String c){
Pattern pattern = Pattern.compile("^(0|[1-9][0-9]*)$");
Matcher matcher = pattern.matcher(c);
boolean res = matcher.find();
return res;
}
}
