Infix expression is a familiar mathematical formula . as ：3 + 6 - 18 / 2 or 3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20.
Our goal is to achieve a calculator , To evaluate an expression based on an infix expression . Expressions are composed of numbers and + - * / () form . Using two stacks to implement , A numerical stack , A symbol stack .

Here we assume that the expressions are all correct , And the number is separated from the symbol by a space . In the code, it is no longer necessary to determine whether the expression format is correct .

<> Realization ideas

The first thing to be sure is , Operators have priority . Consider the situation without brackets first .
We agreed + - The priority of the operator is 1,* / The priority of the operator is 2,

<> Bracketed condition

Without brackets , We just need to calculate the high priority formula first , And then go back to the formula of low priority . As shown in the figure below

The process is as follows ：

* Split expression first
* Traversal expression in turn
* If it's an operator , Direct push
* If it's a number , First, judge whether the value stack is empty , If empty , Then directly into the stack ; If the value stack is not empty , Check the symbol priority at the top of the symbol stack , If it is 2（* /
）, Then take out the value stack top element and symbol stack top element and calculate them , And put the calculation results back into the numerical stack , If the priority is 1（+ -） Then directly into the stack .
* After traversal , There's only one left in the symbol stack + -.
* Traversal symbol stack , Get operator from top of stack , Then take two values from the value stack , And then do the calculation , And re stack the results . Repeat this operation , Until the symbol stack is empty .
<> Bracketed situation

The bracketed situation is more complicated than the bracketed situation , We need to treat the expression in parentheses as a complete subexpression . If you meet the preceding bracket, it's a dividing point , The operation in brackets still follows the principle of prior operation with high priority , Just don't wait for the last calculation with low priority . Instead, the top-down traversal of the symbol stack is started after encountering parentheses . Until the end of traversal .

After traversal, we can't continue to do expression traversal , Instead, check whether the symbol priority at the top of the symbol stack is 2. If is 2, Then take the stack top operator , Then take two values from the value stack , And then do the calculation , And put the results back into the numerical stack .

Repeat the above steps , Until the symbol stack top operator priority is 1 Or stack top symbol is (.

<> code implementation
package com.codestd.study.stack; import org.apache.commons.lang3.StringUtils;
import java.util.Stack; /** * Infix expression * * @author jaune * @since 1.0.0 */ public
class InfixExpression { /** * Evaluate the value of an expression * @param expression expression , Values and symbols must be separated by spaces . */
public int calculate(String expression) { String[] strings = StringUtils.split(
expression, ' '); // Value stack Stack<Integer> numStack = new Stack<>(); // Symbol stack Stack<
String> operStack = new Stack<>(); for (String s : strings) { if (isNumber(s)) {
// Numerical processing if (numStack.isEmpty()) { // If the value stack is empty , Direct push numStack.push(Integer.parseInt
(s)); } else if (isOpeningBracket(operStack.peek())) { // If the top of the symbol stack is a parenthesis , Direct push
numStack.push(Integer.parseInt(s)); } else if (getPriority(operStack.peek()) ==
2) { // If the operator at the top of the symbol stack has a high priority , Take out the top element of the symbol stack , Take out the top element of the numerical stack and calculate it // And put the calculation results back into the numerical stack int num1 =
numStack.pop(); int num2 = Integer.parseInt(s); int res = this.calc(num1, num2,
operStack.pop()); numStack.push(res); } else { // In other cases, directly enter the value stack numStack.push(
Integer.parseInt(s)); } } else if (isBracket(s)) { // Bracket handling if (isOpeningBracket(
s)) { // If it's the preceding bracket, directly enter the symbol stack operStack.push(s); } else { // If it is a parenthesis, the calculation of subexpressions in parenthesis is completed this.
calcBracket(numStack, operStack); } } else if (isOperator(s)) { // Operator handling
operStack.push(s); } } // The operators and values in the symbol stack and the value stack are taken out successively for calculation 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(); } /** *
Evaluate expressions in parentheses */ private void calcBracket(Stack<Integer> numStack, Stack<String>
operStack) { // (12) if (isOpeningBracket(operStack.peek())) { operStack.pop();
highPriorityCalc(numStack, operStack); } else { //
Rules calculated first by priority , Multiplication and division do not appear in parentheses , So sequence calculation is enough . int num2 = numStack.pop(); int num1 =
numStack.pop(); int res = this.calc(num1, num2, operStack.pop()); numStack.push(
res); calcBracket(numStack, operStack); } } /** * Operation of high priority operator */ 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(" Unrecognized symbol "); } 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(
" This symbol is not recognized "); } } }
The test code is as follows
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); } }
The above code has passed this test code .

Technology
Daily Recommendation
views 5