For example, for the infix expression “(A+B)*C-(D+E)/F”, the inverse Polish expression should be “AB+C*DE+F/-“, so that when evaluating the expression, the stack can ignore the precedence of parentheses. For example, to compute the inverse Polish expression, you can compute A+B to get the result and then push it on the stack, then pop the first two elements, then pop the operator *, then compute the result and then push it on the stack. Thus, the last element stored on the stack is the result of the expression.
Let’s see how we can convert an infix expression to an inverse Polish expression.
The first step is to use two stacks, S1 and S2, which are used to temporarily store operators. One of the rules is that operators get higher priority as you go up the stack. Stack S2 is used to input inverse Polish expressions.
General idea:
S1 temporarily stores the operator, but ensures that it takes higher precedence as you go to the top of the stack, and then places the numeric elements in S2.
If the priority of the operator X is less than that of the top of the stack in S1, the top of the stack in S1 is moved to S2 until the priority of the top of the stack in S1 is less than X, at which point X is pushed into S1.
If we run into parentheses while iterating through an expression, if we run into an open parenthesis ‘(‘, we put the open parenthesis in S1 first, and when we run into a close parenthesis ‘)’, we move the S1 open parenthesis to the top of the stack into S2. And of course this open parenthesis, this close parenthesis is going to drop, S1 pops up. Only operators between open parentheses and close parentheses are preserved.
If a number is encountered while iterating through the expression, it is pushed S2.
For the expression “(A+B)*C-(D+E)/F”, do the same.
-
First push the minimum priority operator “#” into the stack S1 to reduce subsequent null-detection.
-
The first operator, with parenthesis “(“, is pushed S1. The second A, with non-operator, is pushed S2. Then the third character is “+”, which is pushed directly into S1 because of the open bracket at the top of the stack, and the fourth character is B, which is pushed into S2. As shown below:
-
When close parenthesis is encountered, + pops S1, pushes S2, and pops open parenthesis (
-
At this point, “*” is scanned, which has higher priority than #, and pushed S1. Next, “C” is scanned, and the non-operator is pushed S2.
-
When a minus sign “-” is encountered, the priority of “*” is compared with that of “*” at the top of S1 stack, and “**” is popped and pressed into S2. The minus sign – is pushed into S1.
-
Open parenthesis “(” is scanned and pushed S1. Scan D, push S2. The plus sign “+” is scanned, and since the top of the stack is “(“, it is directly pushed into S1. Scan E, push S2.
-
This time encountered close parenthesis, according to the last rule processing.
-
When the divisor/is encountered, the priority of the divisor is higher than that of the – at the top of S1.
-
When F is encountered, push S2. The final inverse Polish operator is obtained by scanning all the characters and finally pushing all the characters that are not “#” in S1 into S2.
Then let’s implement the code:
public void RPN(Deque<String> stack1,Deque<String> stack2,String s){
char[] chars = s.toCharArray();
// The following operations are to avoid the occurrence of multiple digits such as 123+234, so do a good job of preprocessing
List<String> sb = new ArrayList<>();
sb.add(String.valueOf(chars[0]));
for(int i=1; i<chars.length; i++){// If the last character was a number and the current character is also a number, calculate a new number and put it in sb
if(Character.isDigit(chars[i-1]) && Character.isDigit(chars[i])){
int last = Integer.valueOf(sb.get(sb.size()-1));
last =last*10;
last = last + chars[i]-'0';
sb.remove(sb.size()-1);
sb.add(String.valueOf(last));
}else{ sb.add(String.valueOf(chars[i])); }}//# indicates the lowest priority, reducing stack1 nulls
stack1.push("#");
for(int i=0; i<sb.size(); i++){ String c = sb.get(i);switch (c){
// Ignore Spaces
case "": break;
// when '(' is pushed directly to 1
case "(" :
stack1.push(c); break;
// When '(' is encountered, the operators between the nearest '(' to the top of s1 are pushed out of the stack one by one, and s2 is discarded.
case ")":
while(! stack1.peek().equals("(")){
stack2.push(stack1.pop());
}
stack1.pop();
break;
// See the following operators:
//1. If the top element of s1 is '(', then x is pushed directly into s1;
//2. If the top element of s1 is not '(', then compare x with the top element of s1.
// If the priority of x is greater than that of the top of the stack s1, then x is pushed directly into the stack s1.
// Otherwise, push the top of s1 into S2 until the top of S1 is lower than the priority of X, or the top of S2 is '(', at which point x is pushed into S1
case "+":
case "-":
case "*":
case "/":
if(stack1.peek().equals("(")){
stack1.push(c);
}
else{
if(getPriority(c)>getPriority(stack1.peek())){
stack1.push(c);
}else{
while (getPriority(stack1.peek())>=getPriority(c)|| stack2.peek().equals("(")){ stack2.push(stack1.pop()); } stack1.push(c); }}break;
default:
stack2.push(c);
break; }}while(! stack1.isEmpty() && ! stack1.peek().equals("#")){ stack2.push(stack1.pop()); }}public int getPriority(String c){
switch (c){
case "#":
return 0;
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
default:return 0; }}Copy the codeBy the way, the calculation code based on the inverse Polish operator is also listed:
public int calculate(String s) {
Deque<String> stack1 = new ArrayDeque<>();
Deque<String> stack2= new ArrayDeque<>();
s = s.trim();
if (s.charAt(0) = =The '-')
s = "0" + s;
// Convert the infix expression to the inverse Polish operator
RPN(stack1,stack2,s);
/** * Computates the inverse Polish operator * by using a helper stack to pop the left element from S2 into the help helper stack. * If it is a number, it is placed directly in help. * If it is an operator, the top two elements of help are used to operate on this operator. The results are then pushed into the help stack. * And so on until the entire S2 stack is traversed. * The result is the top element of help. * /
Deque<Integer> help = new ArrayDeque<>();
while(! stack2.isEmpty()){if(stack2.peekLast().equals("+")) {int a = help.pop();
int b = help.pop();
a=a+b;
stack2.pollLast();
help.push(a);
}
else if(stack2.peekLast().equals("-")) {int a = help.pop();
int b = help.pop();
a=b-a;
stack2.pollLast();
help.push(a);
}
else if(stack2.peekLast().equals("*")) {int a = help.pop();
int b = help.pop();
a=a*b;
stack2.pollLast();
help.push(a);
}
else if(stack2.peekLast().equals("/")) {int a = help.pop();
int b = help.pop();
a=b/a;
stack2.pollLast();
help.push(a);
}
else{ help.push(Integer.valueOf(stack2.pollLast())); }}return help.peek();
}
Copy the code