This is the thirteenth day of my participation in the August Wen Challenge.More challenges in August
1, what is the inverse Polish form (suffix expression)
The inverse Polish expression is also called suffix expression, the kind of expression learned in middle school is called infix expression.
For example, 5×(6+3)÷3-1, 3×(4÷(2+1)×2)-3
These two expressions in this example are infix expressions. Here are two postfix expressions:
+ x 3 present 1-563, 3421 + 2 x 3 – present
Second, the required
1) Enter an inverse Polish expression (suffix expression), use the Stack, and calculate the result
2) Support parentheses and multidigit integers, because here we are mainly talking about data structures, so the calculator is simplified, only support the calculation of integers.
Third, the suffix expression of the calculator evaluation
When encountering a number, push the number onto the stack. When encountering an operator, pop up two numbers at the top of the stack. Use the operator to calculate them accordingly (the second top element and the top element of the stack), and push the result onto the stack. Repeat the process until you reach the right end of the expression, and the resulting value is the result of the expression
For example :(3+4)×5-6 the suffix expression is 3, 4 + 5 × 6 –
It’s easy to understand if we look at the following graph:
Let me explain again:
1) Scan from left to right, pushing 3 and 4 onto the stack;
2) The + operator is encountered, so pop 4 and 3(4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, then push 7, push 5;
3) Next comes the × operator, so pop 5 and 7, calculate 7×5=35, push 35, push 6;
4) Finally, the – operator computes the value of 35-6, which is 29, from which the final result is obtained
Four, code implementation
package Suanfa; import java.util.ArrayList; import java.util.List; import java.util.Stack; Public class PolandNotation {public static void main(String[] args) {// Define the inverse PolandNotation (suffix expression) // (3+4) *5-6 => 3 4 + 5 * 6 - =>29 String suffixExpression = "3 4 + 5 * 6 -"; Add 3 4 + 5 * 6 - => to the ArrayList //2. List<String> List = getListString(suffixExpression); System.out.println("rpnList=" +list); int res = calculate(list); System.out.println(" = "+res); } // Take an inverse Polish expression, Public static List<String> getListString(String suffixExpression){// Split suffixExpression into String[] split = suffixExpression.split(" "); List<String> list = new ArrayList<String>(); for(String ele:split){ list.add(ele); } return list; } public static int calculate(List<String> ls){Stack<String> Stack = new Stack<String>(); If (item.matches("\\d+")) {stack.push(item); } else {int num2 = integer.parseint (stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if(item.equals("+")){ res = num1 + num2; } else if(item.equals("-")){ res = num1 - num2; } else if(item.equals("*")){ res = num1 * num2; } else if(item.equals("/")){ res = num1 / num2; } else {throw new RuntimeException(" operator error ~~"); } // add res to stack.push("" + res); Return integer.parseint (stack.pop()); return integer.parseint (stack.pop()); }}Copy the code