C++ 9ms solution, Stack


  • 0
    M
    class Solution {
    public:
        int operation(char op, int op1, int op2){
            if (op == '+') {return op1 + op2;}
            if (op == '-') {return op1 - op2;}
            if (op == '*') {return op1 * op2;}
            if (op == '/') {return op1 / op2;}
        }
        
        int evalRPN(vector<string>& tokens) {
            stack<int> operands;
            for (int i = 0; i < tokens.size(); i++) {
                if (tokens[i].size() == 1 && (tokens[i][0] == '+' || tokens[i][0] == '-' || tokens[i][0] == '*' || tokens[i][0] == '/')) {
                    int op2 = operands.top();
                    operands.pop();
                    int op1 = operands.top();
                    operands.pop();
                    operands.push(operation(tokens[i][0], op1, op2));
                } else {
                    operands.push(stoi(tokens[i]));
                }
            }
            return operands.top();
        }
    };
    

    Example:

    Consider sample input: ["5", "12", "4", "3", "*", "/", "+"]

    • Build a stack with the raw operands
    • Working downward from the top of your stack, evaluate 2 operands for each consecutive expression, and add the result as a new operand.
    • When the loop concludes, there will be one operand remaining on the stack (the solution)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.