150. Evaluate Reverse Polish Notation

Difficulty: Medium

Frequency: N/A

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

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

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.empty()) return 0;
        int n = tokens.size(), result;
        stack<int> s;
        for (int i = 0; i < n; i++) {
            string tmp = tokens[i];
            if (tmp == "+" || tmp == "-" || tmp == "*" || tmp == "/") {
                int num2 = s.top();
                s.pop();
                int num1 = s.top();
                s.pop();
                if (tmp == "+") {
                    result = num1 + num2;
                } else if (tmp == "-") {
                    result = num1 - num2;
                } else if (tmp == "*") {
                    result = num1 * num2;
                } else {
                    result = num1 / num2;
                }
                s.push(result);
            } else {
                s.push(stoi(tmp));
            }
        }
        return s.top();
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

Advertisements

One thought on “150. Evaluate Reverse Polish Notation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s