中綴表達(dá)式就是我們所熟悉的數(shù)學(xué)算式碎浇。如：3 + 6 - 18 / 2或3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20。
我們的目標(biāo)是要實(shí)現(xiàn)一個(gè)計(jì)算器麦射，來根據(jù)中綴表達(dá)式計(jì)算表達(dá)式的值捶惜。表達(dá)式由數(shù)字和+ - * / ()組成。使用兩個(gè)棧來實(shí)現(xiàn)，一個(gè)數(shù)值棧得封，一個(gè)符號(hào)棧埋心。
在這里我們假設(shè)表達(dá)式都是正確的，并且數(shù)值與符號(hào)之間由空格隔開忙上。在代碼中不再判斷表達(dá)式的格式是否正確拷呆。
實(shí)現(xiàn)思路
首先要確定的是，運(yùn)算符是有優(yōu)先級(jí)的疫粥。先來考慮沒有括號(hào)的情況茬斧。
我們約定+ -運(yùn)算符的優(yōu)先級(jí)為1，* /運(yùn)算符的優(yōu)先級(jí)為2梗逮，
無括號(hào)情況
在沒有括號(hào)時(shí)项秉，我們只需要先計(jì)算優(yōu)先級(jí)高的式子，再回過頭來計(jì)算優(yōu)先級(jí)低的式子即可慷彤。入下圖所示
流程如下：
- 先分割表達(dá)式
- 依次遍歷表達(dá)式
- 如果是運(yùn)算符娄蔼，直接入棧
- 如果是數(shù)字，先判斷數(shù)值棧是否為空底哗，如果為空岁诉，則直接入棧；若數(shù)值棧不為空跋选，查看符號(hào)棧棧頂?shù)姆?hào)的優(yōu)先級(jí)涕癣，如果是2（
* /），則取出數(shù)值棧棧頂元素和符號(hào)棧棧頂元素然后進(jìn)行計(jì)算前标，并將計(jì)算結(jié)果重新入數(shù)值棧坠韩，如果優(yōu)先級(jí)是1（+ -）則直接入棧。
- 遍歷結(jié)束后炼列，符號(hào)棧中就只剩下了
+ -同眯。 - 遍歷符號(hào)棧，從棧頂取出運(yùn)算符唯鸭，然后從數(shù)值棧中取出兩個(gè)數(shù)值须蜗，然后進(jìn)行運(yùn)算，并將運(yùn)算結(jié)果重新入棧。重復(fù)此操作明肮，直到符號(hào)棧為空菱农。
有括號(hào)的情況
有括號(hào)的情況會(huì)比無括號(hào)的情況復(fù)雜一些，我們需要將括號(hào)內(nèi)的表達(dá)式看成一個(gè)完整的子表達(dá)式柿估。遇到前括號(hào)就算是一個(gè)分界點(diǎn)循未，括號(hào)內(nèi)的運(yùn)算依然遵循，優(yōu)先級(jí)高的先運(yùn)算的原則秫舌，只是不再等待最后計(jì)算優(yōu)先級(jí)低的運(yùn)算的妖。而是遇到后括號(hào)后就要開始符號(hào)棧的自頂而下的遍歷。只到遇到前括號(hào)遍歷結(jié)束足陨。
遍歷結(jié)束后還不能繼續(xù)做表達(dá)式的遍歷嫂粟，而是應(yīng)該查看符號(hào)棧棧頂?shù)姆?hào)優(yōu)先級(jí)是否為2。如果為2墨缘，則取出棧頂運(yùn)算符星虹，再?gòu)臄?shù)值棧中取兩個(gè)數(shù)值，然后進(jìn)行運(yùn)算镊讼，并將運(yùn)算結(jié)果重新入數(shù)值棧宽涌。
重復(fù)以上步驟，直到符號(hào)棧棧頂運(yùn)算符有限級(jí)為1或棧頂符號(hào)為(蝶棋。
代碼實(shí)現(xiàn)
package com.codestd.study.stack;
import org.apache.commons.lang3.StringUtils;
import java.util.Stack;
/**
* 中綴表達(dá)式
*
* @author jaune
* @since 1.0.0
*/
public class InfixExpression {
/**
* 計(jì)算表達(dá)式的值
* @param expression 表達(dá)式卸亮，數(shù)值與符號(hào)之間必須用空格隔開。
*/
public int calculate(String expression) {
String[] strings = StringUtils.split(expression, ' ');
// 數(shù)值棧
Stack<Integer> numStack = new Stack<>();
// 符號(hào)棧
Stack<String> operStack = new Stack<>();
for (String s : strings) {
if (isNumber(s)) { // 數(shù)值處理
if (numStack.isEmpty()) {
// 如果數(shù)值棧為空玩裙，直接入棧
numStack.push(Integer.parseInt(s));
} else if (isOpeningBracket(operStack.peek())) {
// 如果符號(hào)棧棧頂是前括號(hào)嫡良，直接入棧
numStack.push(Integer.parseInt(s));
} else if (getPriority(operStack.peek()) == 2) {
// 如果符號(hào)棧棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)高，則取出符號(hào)棧棧頂元素献酗，取出數(shù)值棧棧頂元素然后進(jìn)行計(jì)算
// 并將計(jì)算結(jié)果重新入數(shù)值棧
int num1 = numStack.pop();
int num2 = Integer.parseInt(s);
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
} else {
// 其他情況直接入數(shù)值棧
numStack.push(Integer.parseInt(s));
}
} else if (isBracket(s)) { // 括號(hào)處理
if (isOpeningBracket(s)) {
// 如果是前括號(hào)直接入符號(hào)棧
operStack.push(s);
} else {
// 如果是后括號(hào)則完成括號(hào)內(nèi)子式的計(jì)算
this.calcBracket(numStack, operStack);
}
} else if (isOperator(s)) { // 運(yùn)算符處理
operStack.push(s);
}
}
// 依次取出符號(hào)棧和數(shù)值棧內(nèi)的運(yùn)算符和數(shù)值進(jìn)行計(jì)算
while (!operStack.isEmpty()) {
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
}
return numStack.pop();
}
/**
* 計(jì)算括號(hào)內(nèi)的表達(dá)式
*/
private void calcBracket(Stack<Integer> numStack, Stack<String> operStack) {
// (12)
if (isOpeningBracket(operStack.peek())) {
operStack.pop();
highPriorityCalc(numStack, operStack);
} else {
// 經(jīng)過優(yōu)先級(jí)高先計(jì)算的規(guī)則寝受，括號(hào)內(nèi)不會(huì)出現(xiàn)乘法和除法，所以順序計(jì)算即可罕偎。
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
calcBracket(numStack, operStack);
}
}
/**
* 高優(yōu)先級(jí)運(yùn)算符的運(yùn)算
*/
private void highPriorityCalc(Stack<Integer> numStack, Stack<String> operStack) {
if (this.isOperator(operStack.peek()) && this.getPriority(operStack.peek()) == 2) {
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
highPriorityCalc(numStack, operStack);
}
}
private int calc(int num1, int num2, String s) {
int res;
switch (s) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "/":
res = num1 / num2;
break;
case "*":
res = num1 * num2;
break;
default:
throw new RuntimeException("不能識(shí)別的符號(hào)");
}
return res;
}
private boolean isNumber(String s) {
return s.matches("\\d+");
}
private boolean isOperator(String s) {
return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s);
}
private boolean isBracket(String s) {
return "(".equals(s) || ")".equals(s);
}
private boolean isOpeningBracket(String s) {
return "(".equals(s);
}
private int getPriority(String s) {
if ("+".equals(s) || "-".equals(s)) {
return 1;
} else if ("*".equals(s) || "/".equals(s)) {
return 2;
} else {
throw new RuntimeException("不識(shí)別此符號(hào)");
}
}
}
測(cè)試代碼如下
public class InfixExpressionTest {
@Test
public void test() {
String expression = "3 + 6 - 18 / 2";
InfixExpression ie = new InfixExpression();
int res = ie.calculate(expression);
assertThat(res).isEqualTo(0);
}
@Test
public void test2() {
String expression = "3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20"; // 3+3*18/2-18=3+27-18=12
InfixExpression ie = new InfixExpression();
int res = ie.calculate(expression);
assertThat(res).isEqualTo(12);
}
}
以上代碼已通過此測(cè)試代碼很澄。
