I left a problem at the end of the last article, evaluating the expression 4 + 2 * 3-10/5.
To the computer, all it sees is a string of operators and numbers entered by the user. To keep things simple, we will discuss only the four most common operations: addition, subtraction, multiplication and division. So how do you parse the operators and numbers and how do you deal with the precedence of the operators?
We can solve this problem with the stack we learned in the previous article, where we need two stacks, one for numbers and one for operators. Here I’ll show you how to evaluate the expression 4 + 2 * 3-10/5 step by step:
To parse out the operators and operators we need to traverse the expression from left to right. When it encounters a number, it continues to traverse backwards until it hits an operator.
To parse the numbers correctly, we define the index variable, which starts at 0 and points to the first element of the string.
I’m going to keep going backwards
In Java, the substring(index, I) method is used to assign the value of variable I to index, which is used to intercept the next operand.
Next, determine if the stack is empty, and if so, push the current operator directly onto the stack. Otherwise, peek is used to obtain the top element of the operator stack and compare the priority of the current operator with that of the top element of the operator stack. If the current operator has a higher priority than the element at the top of the stack, the current operator is also pushed onto the stack.
If the priority is lower or the same as that of the top element, the pop operator is taken from the top of the operand stack, and two operands are taken from the top of the operand stack, and the result is pushed onto the operand stack. I’ve drawn a picture to help you understand.
After the above calculation is complete, the current operator is pushed onto the stack and the loop continues backwards.
To enable the stack to support characters and numbers, I extend the ArrayStack class from the previous article to include isEmpty() and peek() methods. The complete code looks like this:
public class ArrayStack<T> {
private Object[] items;
private final int stackSize;
private int top;
public ArrayStack(int stackSize) {
this.stackSize = stackSize;
items = new Object[stackSize];
}
public boolean push(Object item) {
if(top == stackSize) {
System.out.println("Stack full");
return false;
}
items[top++] = item;
return true;
}
public T pop(a) {
if(top == 0) {
System.out.println("Stack empty");
return null;
}
return (T)items[--top];
}
/** * returns the top element *@return* /
public T peek(a) {
if(top == 0) {
System.out.println("Stack empty");
return null;
}
return (T)items[top-1];
}
/** * Check whether the stack is empty *@return* /
public boolean isEmpty(a) {
return top == 0;
}
public void list(a) {
for(int i = top-1; i >=0; i--) { System.out.println(items[i]); }}}Copy the codeExpression evaluation
public class MathExpress {
public static void main(String[] args) {
String express = "4 + 2 + 3 times 10/5";
// Operand stack
ArrayStack<Double> numStack = new ArrayStack(10);
// Operator stack
ArrayStack<Character> opStack = new ArrayStack(10);
// Records the starting position of a number, which is used to intercept a number from a string
int index = 0;
for(int i = 0, len = express.length(); i < len; i++) {
char c = express.charAt(i);
if(c == '+' || c == The '-' || c == The '*' || c == '/') {
// Intercepts the number from the string
String value = express.substring(index, i).trim();
Double num = Double.parseDouble(value);
numStack.push(num);
index = i + 1;
// If the operator stack is empty, it is pushed directly
if(opStack.isEmpty()) {
opStack.push(c);
// Continue the next loop
continue;
}
// Fetch the top of the stack operator
Character op = opStack.peek();
if(compare(c, op) > 0) {
// If the priority of the current operator is higher than that of the top-stack operator, the current operator is directly pushed onto the stack
opStack.push(c);
} else {
// If the priority of the current operator is lower than or equal to that of the top of the stack, then two operands from the stack and the top of the stack are computed
Double v1 = numStack.pop();
Double v2 = numStack.pop();
double res = calc(v1, v2, opStack.pop());
// Add the result to the operand stack
numStack.push(res);
// push the current operator onto the stackopStack.push(c); }}// The last number
if(i == len - 1) { Double num = Double.parseDouble(express.substring(index, len).trim()); numStack.push(num); }}// Calculate the final result
while(! opStack.isEmpty()) { Double v1 = numStack.pop(); Double v2 = numStack.pop();double res = calc(v1, v2, opStack.pop());
numStack.push(res);
}
System.out.println(express +"=" + numStack.pop());
}
/** * count *@param v1
* @param v2
* @param c
* @return* /
public static double calc(double v1, double v2, char c) {
switch (c) {
case '+':
return v2 + v1;
case The '-':
return v2 - v1;
case The '*':
return v2 * v1;
case '/':
return v2 / v1;
default:
throw new IllegalArgumentException("Unsupported operators"+ c); }}/** * compare operator priority *@param c1
* @param c2
* @return* /
public static int compare(char c1, char c2) {
return priority(c1) - priority(c2);
}
/** * gets the operator priority *@param c
* @return* /
private static int priority(char c) {
if(c == '+' || c == The '-') {
return 0;
}else if(c == The '*' || c == '/') {
return 1;
}
throw new IllegalArgumentException("Unsupported operators"+ c); }}Copy the code“More exciting content please pay attention to the public number geekyMV, like please share to more friends oh”
