Polish expression& Infix expression& Reverse Polish expression& Infix expression invert to Reverse Polish expression
- 字首表達式(Polish expression, 波蘭表達式)
- 中綴表達式(Infix expression)
- 字尾表達式(Reverse Polish expression, 逆波蘭表達式)
-
- 中綴表達式(Infix expression): 實作簡單電腦
- 字尾表達式(Reverse Polish expression, 逆波蘭表達式): 實作簡單電腦
- 中綴表達式轉換字尾表達式(Infix expression invert to Reverse Polish expression)
字首表達式(Polish expression, 波蘭表達式)
- 字首表達式的運算符位于操作數之前 如
中綴表達式
- 運算過程: 從右往左掃描表達式, 将數字按5,7,4,3的順序壓入棧中, 讀到運算符+時彈出兩個數(3和4), 運算後, 再将結果7壓入棧内, 再讀到運算符時彈出兩個數(77), 運算後, 再将結果49壓入棧内, 再讀到運算符-時彈出兩個數(49-5), 運算後, 再将結果44壓入棧内, 即完成運算
* 字首表達式的運算順序已經規劃好了, 是以無需判斷運算符的優先級
中綴表達式(Infix expression)
- 中綴表達式就是最常見的運算表達式 如 (3+4)*7-5. 此表達式需判斷運算符的優先級
字尾表達式(Reverse Polish expression, 逆波蘭表達式)
- 與字首表達式相似, 隻是運算符位于操作數後面 如
中綴表達式
- 運算過程: 從左往右掃描表達式, 将數字3,4壓入棧中, 讀到運算符+時彈出兩個數(3和4), 運算後, 再将結果7壓入棧内, 再下一個數字7壓入棧内, 再讀到運算符時彈出兩個數(77), 運算後, 再将結果49壓入棧内, 再繼續将下一個數字5壓入棧内, 再讀到運算符-時彈出兩個數(49-5), 運算後, 再将結果44壓入棧内, 即完成運算
中綴表達式(Infix expression): 實作簡單電腦
- 思路分析
- 定義兩個棧: 一個是數值棧, 另一個運算符棧
- 定義兩個方法: 判斷運算符優先級的方法和計算已入棧數值的方法
- 逐個循環掃描輸入的中綴表達式, 如果是數字就入數值棧, 如果是運算符, 則需要與運算符棧的棧頂運算符比較優先級. 如果優先級高于棧頂的運算符, 則直接入棧(運算符棧), 否則, 從數值棧取2元素(數值), 在從運算符棧取棧頂元素做運算, 将運算結果再存入數值棧, 之後将目前運算符入棧(運算符棧)
- 執行個體代碼:
/** 定義數組棧*/
class ArrayStack {
/** 棧大小*/
private int maxSize;
/** 通過該數組存放資料, 模拟棧資料結構*/
private int[] stack;
/** 棧頂的 index, 初始值為-1*/
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
/** 棧滿*/
public boolean isFull() {
return top == maxSize - 1;
}
/** 棧空*/
public boolean isEmpty() {
return top == -1;
}
/** 入/壓棧*/
public void push(int value) {
if (isFull()) {
System.out.println("入棧失敗, 棧已滿!");
return;
}
top++;
stack[top] = value;
}
/** 出/彈棧*/
public int pop() {
if (isEmpty()) {
throw new RuntimeException("出棧失敗, 沒有資料!");
}
int value = stack[top];
top--;
return value;
}
/** 從棧頂開始列印所有内容*/
public void list() {
if (isEmpty()) {
System.out.println("列印失敗, 沒有資料!");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
/** 檢視棧頂元素内容*/
public int peek() {
return stack[top];
}
/** 運算符的優先級*/
public int operPriority(int oper) {
if (oper == '*'|| oper == '/') {
return 1;
} else if(oper == '+'|| oper == '-') {
return 0;
} else {
/** 無效的表達式*/
return -1;
}
}
/** 判斷是不是一個運算符*/
public boolean isOper(char val) {
return val == '+' || val=='-' || val=='*' || val=='/';
}
/** 計算方法*/
public int cal(int num1, int num2, int oper) {
int res = 0;
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}
public class CalculatorApp {
public static void main(String[] args) {
System.out.println("請輸入要計算的中綴表達式: ");
Scanner in = new Scanner(System.in);
String expression = in.nextLine();
in.close();
/** 定義數值棧*/
ArrayStack numStack = new ArrayStack(10);
/** 定義運算符棧*/
ArrayStack operStack = new ArrayStack(10);
/** 表達式每個字元位索引*/
int index = 0;
/** 每次循環擷取到的字元*/
char ch;
/** 計算多位數時, 用于拼接的字元串變量*/
String keepnum = "";
/** 當計算時, 從數值棧出棧的第一個數值*/
int num1 = 0;
/** 當計算時, 從數值棧出棧的第而二個數值*/
int num2 = 0;
/** 運算符 char <-> int*/
int oper = 0;
/** 計算結果*/
int res = 0;
while (true) {
/** 每次循環擷取單個字元*/
ch = expression.substring(index, index + 1).charAt(0);
/** 判斷是否為運算符*/
if (operStack.isOper(ch)) {
if (operStack.isEmpty()) {
/** 如果定義運算符棧為空, 直接入棧*/
operStack.push(ch);
} else {
/** 判斷目前運算符(如 +)的優先級是否低于棧頂運算符(如 x), 如果低或相等通過*/
if (operStack.operPriority(ch) <= operStack.operPriority(operStack.peek())) {
/** 之前已入棧的數值與運算符取出, 開始計算*/
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = operStack.cal(num1, num2, oper);
/** 數值棧的累計值計算後, 将值重新入棧*/
numStack.push(res);
/** 目前運算符(如 +), 入棧*/
operStack.push(ch);
} else {
operStack.push(ch);
}
}
} else {
/**
* 1. 如果電腦隻做單數的運算, 可以直接入棧 numStack.push(ch - 48);
* 2. 如果支援多位數, 需要往下一位判斷是否為數值而不是運算符. 如果下一位是運算符就可以 numStack.push(keepnum)
* */
/** 循環拼接多位數( 如 12, 2, 6, 123)*/
keepnum += ch;
/** 如果是最後一位, 不再做下一位字元的判斷*/
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepnum));
} else {
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
/** 如果下一位是運算符就入棧*/
numStack.push(Integer.parseInt(keepnum));
/** 清空數*/
keepnum = "";
}
}
}
index++;
if (index >= expression.length()) {
/** 最後位, 停止循環*/
break;
}
}
while (true) {
/** 運算符棧為空時, 則計算結束停止循環*/
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = operStack.cal(num1, num2, oper);
numStack.push(res);
}
System.out.printf("%s的結算結構為 %d\n",expression, numStack.pop());
}
}
輸出:
> 請輸入要計算的中綴表達式:
> 12+2*6-123
> 12+2*6-123的結算結構為 -99
字尾表達式(Reverse Polish expression, 逆波蘭表達式): 實作簡單電腦
- 執行個體代碼:
public class CalculatorApp {
/** 将一個逆波蘭表達式, 按各數值與運算符依次放入到 ArrayList中*/
public static List<String> getListString(String expression) {
String[] arr = expression.split(" ");
List<String> list = new ArrayList<>(arr.length);
for(String e: arr) {
list.add(e);
}
return list;
}
/**
* 逆波蘭表達式的運算方法:
* 1. 從左往右掃描表達式, 将數字3,4壓入棧中
* 2. 讀到運算符+時彈出兩個數(3和4), 運算後, 再将結果7壓入棧内
* 3. 再下一個數字5壓入棧内
* 4. 再讀到運算符*時彈出兩個數(7*5), 運算後, 再将結果35壓入棧内
* 5. 再繼續将下一個數字6壓入棧内
* 6. 再讀到運算符-時彈出兩個數(35-6), 運算後, 再将結果29壓入棧内, 即完成運算
* */
public static int cal(List<String> expressionList) {
Stack<String> stack = new Stack<>();
for (String exp : expressionList) {
/** 是否為數值*/
if (exp.matches("\\d+")) {
/** 數值直接入棧*/
stack.push(exp);
} else {
/** 彈出兩個數, 并運算*/
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int res = 0;
if (exp.equals("+")) {
res = num1 + num2;
} else if (exp.equals("-")) {
res = num2 - num1;
} else if (exp.equals("*")) {
res = num1 * num2;
} else if (exp.equals("/")) {
res = num2 / num1;
} else {
throw new RuntimeException("運算符錯誤!");
}
/** 每次運算結果壓入棧*/
stack.push(String.valueOf(res));
}
}
/** 最後留在棧中的數值為運算結果*/
return Integer.parseInt(stack.pop());
}
public static void main(String[] args) {
/**
* 中綴表達式 (3+4)*5-6的字尾表達式為 34+5*6-
* */
String expression = "3 4 + 5 * 6 -";
List<String> expressionList = getListString(expression);
int res = cal(expressionList);
System.out.println("34+5*6-的結算結構為 " + res);
}
}
輸出:
> 34+5*6-的結算結構為 29
中綴表達式轉換字尾表達式(Infix expression invert to Reverse Polish expression)
- 初始化兩個棧: 運算符棧 s1和存儲中間結果的 List s2
- 從左到右掃描中綴表達式
- 遇到操作數時, 将其直接加到 s2
-
遇到運算符時, 将其與 s1棧頂運算符比較優先級:
(1) 如果 s1為空或棧頂運算符為左括号"(", 則直接将此運算符入棧
(2) 否則, 若優先級比棧頂的運算符高, 也将運算符壓入 s1
(3) 否則, 将 s1棧頂的運算符彈出, 并壓入到 s2中, 再次轉到(4-1)與 s1中新的棧頂運算符相比較
-
遇到括号時:
(1) 如果是左括号"(", 則直接壓入 s1
(2) 如果是右括号")", 則依次彈出 s2棧頂的運算符, 并壓入 s2, 直到遇到左括号為止, 再将這一對括号丢棄
- 重複步驟2至5, 直到表達式的最右邊
- 将 s1中剩餘的運算符依次彈出并壓入 s2
- 輸出 s2
- 執行個體代碼:
public class InfixToReversePolishApp {
/** 運算符的優先級*/
public static int operPriority(String oper) {
if (oper.equals("*") || oper.equals("/")) {
return 2;
} else if(oper.equals("+") || oper.equals("-")) {
return 1;
} else {
if (!oper.equals("(") && !oper.equals(")")) {
/** 無效的表達式*/
System.out.println("不存在該運算符" + oper);
}
return 0;
}
}
/** 中綴表達式對應的 String List*/
public static List<String> toInfixStringList(String infixExpression) {
List<String> list = new ArrayList<>();
/** 周遊中綴表達式字元串的索引*/
int index = 0;
/** 計算多位數時, 用于拼接的字元串變量*/
String keepnum;
/** 每次循環擷取到的字元*/
char ch;
while (index < infixExpression.length()) {
/**
* 不是數字, 就直接加到 List
* */
if ((ch = infixExpression.charAt(index)) < 48 || (ch = infixExpression.charAt(index)) > 57) {
list.add(String.valueOf(ch));
index++;
} else {
/** 初始化多位數拼接變量*/
keepnum = "";
/**
* - 不可以為最後數(由于内部循環拼接, 需要做此判斷)
* - 每個字元必須為數字 ASCII: 48~57
* */
while (index < infixExpression.length() && (ch = infixExpression.charAt(index)) >= 48
&& (ch=infixExpression.charAt(index)) <= 57) {
/** 循環拼接多位數*/
keepnum += ch;
index++;
}
list.add(keepnum);
}
}
return list;
}
/** 中綴表達式 List轉換字尾表達式(逆波蘭表達式) List*/
public static String infixToReversePolish(List<String> infixList) {
/** 運算符棧(含括号)*/
Stack<String> s1 = new Stack<>();
/** 存轉換後的字尾表達式, 隻存無取, 直到方法結束傳回. 注: 傳回時需逆序輸出*/
List<String> s2 = new ArrayList<>();
for(String exp: infixList) {
/** 數字直接存入 s2*/
if(exp.matches("\\d+")) {
s2.add(exp);
} else if (exp.equals("(")) {
s1.push(exp);
} else if (exp.equals(")")) {
/** 如果是右括号")", 則依次彈出 s1棧頂的運算符, 并壓入 s2, 直到遇到左括号為止, 再将這一對括号丢棄*/
while(!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();
} else {
/**
* 1. s1不為空
* 2. s1的棧頂運算符(如果是括号會傳回0)大于等于 目前 exp(運算符)的優先級, 便将 s1棧頂彈出棧同時入棧到 s2
* */
while(s1.size() != 0 && operPriority(s1.peek()) >= operPriority(exp) ) {
s2.add(s1.pop());
}
/** 目前 exp(運算符)入棧到 s1*/
s1.push(exp);
}
}
/** 将s1中剩餘的運算符依次彈出棧, 并加到 s2*/
while(s1.size() > 0) {
s2.add(s1.pop());
}
return s2.parallelStream()
.collect(Collectors.joining());
}
public static void main(String[] args) {
/**
* - 中綴表達式 1+((2+3)*4)-5的字尾表達式為 123+4*+5–
* */
String infixExpression = "1+((2+3)*4)-5";
List<String> infixList = toInfixStringList(infixExpression);
System.out.println("中綴表達式對應的 List" + infixList);
String reversePolish = infixToReversePolish(infixList);
System.out.println("字尾表達式對應的 " + reversePolish);
}
}
輸出:
> 中綴表達式對應的 List[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
> 字尾表達式對應的 123+4*+5-
如果您覺得有幫助，歡迎點贊哦 ~ 謝謝!!
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)