This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Description:

Integer division preserves only integer parts. Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

Tokens = ["2","1","+","3","*"] tokens = ["2","1"," 3","*"] Tokens = "4", "13", "5", "/", "+"] output: 6: this formula into common infix arithmetic expression is: (4 +) (13/5) = 6 example 3: input: Tokens = [" 10 ", "6", "9", "3", "+", "11", "*", "/", "*", "17", "+", "5", "+"] output: 22 explanation: this formula into common infix arithmetic expression is: ((10 * (6 / ((9 + 3) * - 11))) + 17) + 5 = ((10 * (6 / (12 * - 11))) + 17) + 5 = ((10 * (6 / - 132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 https://leetcode-cn.com/problems/evaluate-reverse-polish-notation copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

• Today’s daily question is the application of stack. The difficulty of this question is to understand the meaning of the question. After understanding the meaning of the question, we can calmly solve it. First we specify the Reverse Polish notation (RPN, or inverse Polish notation), also known as postfix expressions (writing operators after operands).
• It’s not too difficult to implement an inverse Polish algorithm, but why convert a seemingly simple infix expression into a complex inverse Polish? The reason is that this simplicity is relative to the structure of the human mind, and the order expression is a very complex structure to a computer. The inverse Polish form, by contrast, is relatively straightforward to a computer. Because the memory structure commonly used by computers is a stack structure, it performs a first-in, last-out order. The implementation code is as follows:

Through the code

public class DayCode {
    public static void main(String[] args) {
        String[] s = {"3"."11"."5"."+"."-"};
        int ans = new DayCode().evalRPN(s);
        System.out.println(ans);
    }

    /** * Link: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ * Time complexity O(n) * Space complexity O(n) *@param tokens
     * @return* /
    public int evalRPN(String[] tokens) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            int temp = 0;
            int num1 = 0;
            int num2 = 0;
            switch (token) {
                case "+":
                    temp = stack.removeLast() + stack.removeLast();
                    stack.addLast(temp);
                    break;
                case "-":
                    num1 = stack.removeLast();
                    num2 = stack.removeLast();
                    stack.addLast(num2 - num1);
                    break;
                case "*":
                    temp = stack.removeLast() * stack.removeLast();
                    stack.addLast(temp);
                    break;
                case "/":
                    num1 = stack.removeLast();
                    num2 = stack.removeLast();
                    stack.addLast(num2 / num1);
                    break;
                default:
                    stack.addLast(Integer.parseInt(token));
                    break; }}if(! stack.isEmpty()) { ans = stack.pop(); }returnans; }}Copy the code

The stack can also be used to solve simple calculator problems. * The time complexity of the above algorithm is O(n), space complexity is O(n) * Stick to the daily problem, come on!Copy the code