This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is a 150. Inverse Polish expression evaluation on LeetCode with medium difficulty.

Tag: “Expression evaluation”

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.

Example 1:

Input: tokens = [" 2 ", "1", "+", "3", "*"] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9Copy the code

Example 2:

Input: tokens = "4", "13", "5", "/", "+"] output: 6: this formula into common infix arithmetic expression is: (4 +) = 6 (13/5)Copy the code

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 = 22Copy the code

Tip:

  • 1 <= tokens.length <=
    1 0 4 10^4
  • Tokens [I] are either an operator (“+”, “-“, “*”, or “/”) or integers in the range [-200, 200]

Inverse Polish expression:

An inverse Polish expression is an expression with a suffix, which means the operator is written after it.

  • The usual formula is an infix expression, such as (1 + 2) * (3 + 4).
  • The inverse Polish expression of the formula is (1 2 +) (3 4 +) *).

The inverse Polish expression has two main advantages:

  • After removing the parentheses, the expression has no ambiguity. Even if the above formula is written as 1, 2 + 3, 4 + *, the correct result can be calculated according to the order.
  • Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.

The basic idea

This is a question about “expression calculation”.

All “expression evaluation” problems are related to “stacks”.

In this case, we can create a “number stack” to hold all the numbers, and when we encounter an operator, we can take two numbers from the stack and perform the operation and put the result back on the stack. At the end of the process, the element at the top of the stack is the final result.

The stack is usually implemented in two ways: using arrays to continue simulation & using the system’s own stack structure

Array simulation stack solution

Code:

class Solution {
    public int evalRPN(String[] ts) {
        int[] d = new int[ts.length];
        int hh = 0, tt = -1;
        for (String s : ts) {
            if ("+ - * /".contains(s)) {
                int b = d[tt--], a = d[tt--];
                d[++tt] = calc(a, b, s);
            } else{ d[++tt] = Integer.parseInt(s); }}return d[tt];
    }
    int calc(int a, int b, String op) {
        if (op.equals("+")) return a + b;
        else if (op.equals("-")) return a - b;
        else if (op.equals("*")) return a * b;
        else if (op.equals("/")) return a / b;
        else return -1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Own stack solution

Code:

class Solution {
    public int evalRPN(String[] ts) {
        Deque<Integer> d = new ArrayDeque<>();
        for (String s : ts) {
            if ("+ - * /".contains(s)) {
                int b = d.pollLast(), a = d.pollLast();
                d.addLast(calc(a, b, s));
            }  else{ d.addLast(Integer.parseInt(s)); }}return d.pollLast();
    }
    int calc(int a, int b, String op) {
        if (op.equals("+")) return a + b;
        else if (op.equals("-")) return a - b;
        else if (op.equals("*")) return a * b;
        else if (op.equals("/")) return a / b;
        else return -1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

other

A similar question appeared in last week’s Question of the Day on “expression evaluation” :

  • 224. Basic Calculator: contains the symbol + – ()

  • 227. Basic Calculator II: Contains the symbol + – * /

  • 772. Basic Calculator III: With lock and contains the symbol + – * / ()

  • 770. Basic Calculator IV: Contains custom function symbols

The last

This is the No.150 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.