一、中綴與字尾表達式的介紹
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的字尾形式可以如下定義:
(1)如果E是一個變量或常量,則E的字尾式是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);
}
}