Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「前綴，中綴，后綴」
前綴表達(dá)式(波蘭表達(dá)式)
前綴表達(dá)式又稱波蘭表達(dá)式,前綴表達(dá)式的運(yùn)算符位于操作符之前,如(3+4)*5-6對應(yīng)的前綴表達(dá)式就是- * + 3 4 5 6
前綴表達(dá)式的計算機(jī)求值
從右至左掃描表達(dá)式,遇到數(shù)字時,就壓入堆棧,遇到運(yùn)算符時,彈出棧頂?shù)膬蓚€數(shù),用運(yùn)算符對他們做相應(yīng)的計算(棧頂元素和次頂元素),并將結(jié)果入棧;重復(fù)上述過程直到表達(dá)式最左端,最后運(yùn)算得出的值即為表達(dá)式的結(jié)果.
例如:(3+4)*5-6對應(yīng)的前綴表達(dá)式就是- * + 3 4 5 6,針對前綴表達(dá)式求值步驟如下:
- 從右至左掃描,將6,5,4,3壓入堆棧.
- 遇到+運(yùn)算符,因此彈出3和4(3為棧頂元素,4為次頂元素),計算出3+4的值,得7,再將7入棧.
- 接下來是*運(yùn)算符,因此彈出7和5,計算出35,將35入棧.
- 最后是-運(yùn)算符,計算出35-6的值,即29,由此得出最終結(jié)果.
中綴表達(dá)式
中綴表達(dá)式就是常見的運(yùn)算表達(dá)式,如(3*4)+5-6.中綴表達(dá)式的求值是我們?nèi)俗钍煜さ?但是對計算機(jī)來說卻不好操作,因此在計算結(jié)果時,往往會將中綴表達(dá)式轉(zhuǎn)換成其他表達(dá)式來操作(一般轉(zhuǎn)換成后綴表達(dá)式).
后綴表達(dá)式
后綴表達(dá)式又稱為逆波蘭表達(dá)式,與前綴表達(dá)式類似,只是運(yùn)算符在操作數(shù)之后.
如(3+4)*5-6對應(yīng)的后綴表達(dá)式就是3 4 + 5 * 6 -
再比如
后綴表達(dá)式的計算機(jī)求值
從左至右掃描表達(dá)式,遇到數(shù)字時,將數(shù)字壓入堆棧,遇到運(yùn)算符時,彈出棧頂?shù)膬蓚€元素,用運(yùn)算符對它們做對應(yīng)的計算(棧頂元素和次頂元素),并將結(jié)果入棧,重復(fù)上述過程直到表示最右端,最后運(yùn)算得出的值即為表達(dá)式的結(jié)果.
例如:(3+4)*5-6對應(yīng)的后綴表達(dá)就是 3 4 + 5 * 6 -,針對后綴表達(dá)式求值步驟如下:
- 從左至右掃描,將3和4壓入堆棧.
- 遇到+運(yùn)算符,因此彈出4和3(4為棧頂元素,3為次頂元素),計算出7,再將7入棧.
- 將5入棧.
- 遇到*運(yùn)算符,因此單出5和7,計算出35,將35入棧.
- 將6入棧.
- 最后是-運(yùn)算符,計算出29,由此得出最終結(jié)果.
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
1.初始化兩個棧:運(yùn)算符棧s1和存儲空中間結(jié)果的棧s2.
2.從左至右掃描表達(dá)式.
3.遇到操作數(shù)時,將其壓入s2.
4.遇到運(yùn)算符時,比較其與s1棧頂運(yùn)算符的優(yōu)先級.
- 如果s1為空,或者棧頂運(yùn)算符為左括號"(",則直接將此運(yùn)算符入棧.
- 否則,若優(yōu)先級比棧頂運(yùn)算符的高,也將運(yùn)算符壓入s1.
- 否則,將s1棧頂?shù)倪\(yùn)算符彈出并壓入s2中,再次轉(zhuǎn)到(4.1)與s1中新的棧頂運(yùn)算符相比較.
5.遇到括號時:
- 如果是左括號"(",則直接壓入s1.
- 如果是右括號")",則依次彈出s1棧頂?shù)倪\(yùn)算符,并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄.
6.重復(fù)步驟2至5,直到表達(dá)式最右邊.
7.將s1中剩余的運(yùn)算符依次彈出并壓入s2.
8.依次彈出s2中的元素并輸出,結(jié)果的逆序即為中綴表達(dá)式對應(yīng)的后綴表達(dá)式.
簡單的后綴表達(dá)式計算器
- package com.structures.stack;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.Stack;
- public class PolandNotation {
- public static void main(String[] args) {
- //先給出逆波蘭表達(dá)式(3+4)*5-6==>3 4 + 5 * 6 -
- String expression = "1+(((2+3)*4))-5";
- List<String> toInfixExpressionList = toInfixExpressionList(expression);
- System.out.println(toInfixExpressionList);
- List<String> suffixExpressList = parseSuffixExpressList(toInfixExpressionList);
- System.out.println(suffixExpressList);
- System.out.println(calculate(suffixExpressList));
- /*
- [1, +, (, (, (, 2, +, 3, ), *, 4, ), ), -, 5]
- 不存在該運(yùn)算符
- 不存在該運(yùn)算符
- [1, 2, 3, +, 4, *, +, 5, -]
- 16
- */
- }
- //將中綴表達(dá)式對應(yīng)的List轉(zhuǎn)換成后綴表達(dá)式對應(yīng)的List
- public static List<String> parseSuffixExpressList(List<String> ls) {
- //定義兩個棧
- Stack<String> s1 = new Stack<>();//符號棧
- //說明:因為s2這個棧,在整個轉(zhuǎn)換過程中,沒有pop操作,而且后面還要逆序操作.
- //因此比較麻煩,這里我們就不用Stack<String> 直接使用List<String> s2.
- //Stack<String> s2 = new Stack<>();//存儲中間結(jié)果的棧s2
- List<String> s2 = new ArrayList<>();
- for (String item : ls) {
- if (item.matches("\\d+")) {
- s2.add(item);
- } else if (item.equals("(")) {
- s1.push("(");
- } else if (item.equals(")")) {
- //如果是右括號")",則依次彈出s1棧頂?shù)倪\(yùn)算符,并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄.
- while (!s1.peek().equals("(")) {
- s2.add(s1.pop());
- }
- s1.pop();
- } else {
- //當(dāng)item優(yōu)先級小于等于棧頂運(yùn)算符,將s1棧頂?shù)倪\(yùn)算符彈出并壓入s2中,再次轉(zhuǎn)到(4.1)與s1中新的棧頂運(yùn)算符相比較.
- while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
- s2.add(s1.pop());
- }
- //還需要將item壓入棧
- s1.push(item);
- }
- }
- //將s1中剩余的運(yùn)算符依次彈出并壓入s2
- while (s1.size() != 0) {
- s2.add(s1.pop());
- }
- return s2;
- }
- //將中綴表達(dá)式轉(zhuǎn)List
- public static List<String> toInfixExpressionList(String s) {
- List<String> ls = new ArrayList<>();
- int i = 0;
- String str;//對多位數(shù)拼接
- char c;
- do {
- //如果c是一個非數(shù)字,直接加入ls
- if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57) {
- ls.add("" + c);
- i++;
- } else {
- //如果是一個數(shù),需要考慮多位數(shù)問題.
- str = "";
- while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
- str += c;
- i++;
- }
- }
- } while (i < s.length());
- return ls;
- }
- //根據(jù)逆波蘭表達(dá)式求值
- public static int calculate(List<String> ls) {
- Stack<String> stack = new Stack<>();
- for (String item : ls) {
- //這里使用正則表達(dá)式來取出數(shù),匹配的是多位數(shù)
- if (item.matches("\\d+")) {
- stack.push(item);
- } else {
- int num2 = Integer.parseInt(stack.pop());
- int num1 = Integer.parseInt(stack.pop());
- int res = 0;
- switch (item) {
- case "+":
- res = num1 + num2;
- break;
- case "-":
- res = num1 - num2;
- break;
- case "*":
- res = num1 * num2;
- break;
- case "/":
- res = num1 / num2;
- break;
- default:
- throw new RuntimeException("運(yùn)算符有誤");
- }
- stack.push(res + "");
- }
- }
- return Integer.parseInt(stack.pop());
- }
- }
- //根據(jù)運(yùn)算符返回對應(yīng)的優(yōu)先級數(shù)字
- class Operation {
- private static int ADD = 1;
- private static int SUB = 1;
- private static int MUL = 2;
- private static int DIV = 2;
- public static int getValue(String operation) {
- int result = 0;
- switch (operation) {
- case "+":
- result = ADD;
- break;
- case "-":
- result = SUB;
- break;
- case "*":
- result = MUL;
- break;
- case "/":
- result = DIV;
- break;
- default:
- System.out.println("不存在該運(yùn)算符");
- break;
- }
- return result;
- }
- }
【編輯推薦】
