This is the seventh day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Evaluate the inverse Polish expression

Find the value of 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.

** Inverse Polish expressions: ** See inverse Polish expressions for details

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/ev… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: stack

The value of the inverse Polish expression (suffix expression) is solved by using the last-in-first-out feature of the stack, and the specific solving process is as follows:

  • If the original expression has only one argument, the operand is returned.
  • Otherwise, declare an operand stack numS to store operands, traversing the characters of the inverse Polish expression in order:
    • If the current character is an operand, it is pushed directly.
    • If the current character is an operator, the two operands are removed from the stack and evaluated according to the current operator, recalculating the result.
  • Finally, it returns the only value of the operand stack, which is the evaluation of the inverse Polish expression.
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode_150 {

    public static int evalRPN(String[] tokens) {
        if (tokens.length == 1) {
            return Integer.valueOf(tokens[0]);
        }
        List<String> operatorList = new ArrayList<>();
        operatorList.add("+");
        operatorList.add("-");
        operatorList.add("*");
        operatorList.add("/");

        // Operand stack
        Stack<Integer> nums = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            if (operatorList.contains(tokens[i])) {
                // If it is an operator, take two operands to evaluate and push the result back onto the stack
                int num1 = Integer.valueOf(nums.pop());
                int num2 = Integer.valueOf(nums.pop());
                if ("+".equals(tokens[i])) {
                    nums.push(num2 + num1);
                } else if ("-".equals(tokens[i])) {
                    nums.push(num2 - num1);
                } else if ("*".equals(tokens[i])) {
                    nums.push(num2 * num1);
                } else if ("/".equals(tokens[i])) { nums.push(num2 / num1); }}else {
                // if it is an operand, it is pushednums.push(Integer.valueOf(tokens[i])); }}return nums.pop();
    }

    public static void main(String[] args) {
        // Test case
        String[] tokens = new String[]{"10"."6"."9"."3"."+"."11"."*"."/"."*"."17"."+"."5"."+"};
        / / convert infix expression results are: ((10 * (6 / ((9 + 3) * - 11))) + 17) + 5
        // The result is: 22System.out.println(evalRPN(tokens)); }}Copy the code

Nothing is difficult to the man who will try.