Leetcode-150-Evaluate Reverse Polish Notation

Posted 2022-07-17

9~11 min read

Evaluate Reverse Polish Notation

leetcode: https://leetcode.com/problems/evaluate-reverse-polish-notation/

Description:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Idea:

**solution **

Step1: set the stack to record result

Step2: when the element in the string isn’t operator, add them to stack, if the current element is operation, do the operation according to the operator

Step3: because the operation only take two cloest previous elements before the opeator, so use stack.pop() twice to get two elements and remove them at the same time, push the result of them to the stack.

Step4: when the operation is / or -, it means we need to get the correct order of elements. create two temporary variables to record the two previous elments separately. them use them do the operation and push the result to the stack.

Code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int evalRPN(String[] tokens) {
        //use stack to record result
        Stack<Integer> result = new Stack<>();
        //traverse the string
        for(int i=0; i<tokens.length; i++){
            //because we need to get correct order of two elements, so use temporary variables to store them.
            if(tokens[i].equals("/")){
                int temp1 = result.pop();
                int temp2 = result.pop();
                result.push(temp2/temp1);
            }
            //pop two top elements to complete the operation and remove them.
            else if(tokens[i].equals("+")){
                result.push(result.pop()+result.pop());
            }
            //same situation as /
            else if(tokens[i].equals("-")){
                int temp1 = result.pop();
                int temp2 = result.pop();
                result.push(temp2-temp1);
            }
            //same situation like +
            else if(tokens[i].equals("*")){
                result.push(result.pop()*result.pop());
            }
            else{
                //if the current element isn't operator, convert the string to int and add the element to the stack
                result.push(Integer.valueOf(tokens[i]));
            }
        }
        //get the result, only one element in the stack
        return result.peek();
    }
}


1
2
//convert the string data type to integer data type
Integer.valueOf(tokens[i]);

Leetcode

Leetcode Stack and Queue