【LeetCode OJ】Evaluate Reverse Polish Notation

Problem link:

http://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

According to the wiki page, the algorithm for evaluating any postfix expression is fairly straightforward. The following is the pseudo-code for evaluating a postfix expression.

while there are input tokens left

     read the next token from input

        if the token is a value (operand)

            push it into the stack

        else (the token is an operator)

            let n be the number of the arguments of the operator

            if there are fewer than n values in the stack

                return ERROR (non-sufficient operands in the expression)

            else

                pop the top n values from the stack

                evaluate the expression with the operator and operands

                push the result, if any, back into the stack

if there is only one value in the stack

    return the value as the result

else

    return ERROR (too many operands in the expression)

However, in this problem, it is much easier since there are only four operators. What we need to concern is only to identify the operators and numbers (integer in this case). Therefore, we will implement two functions:

A stack structure
Functions on a string that determine the string is an integer or an operator.

The C++ implementation of the algorithm is as follows.

#include <stack>

#include <ctype.h>

class Solution {

public:

    int evalRPN(vector<string> &tokens) {

        // The stack to store operators (int values) only

        std::stack<int> res;

        int x,y;

        // Iterate the vector from left to right

        for(std::vector<string>::iterator it = tokens.begin(); it != tokens.end(); it++)

        {

            // If operator, pop and evaluate

            if ( (*it).length() == 1 && !isdigit((*it)[0]) ) {

                y = res.top();

                res.pop();

                x = res.top();

                res.pop();

                if (*it == "+") x += y;

                else if (*it == "-") x -= y;

                else if (*it == "*") x *= y;

                else if (*it == "/") x /= y;

                res.push(x);

            }

            // If operand, push it into the stack

            else res.push( atoi((*it).c_str()) );

        }

        // The only value left in the stack is the final result

        return res.top();

    }

};

巴特西

【LeetCode OJ】Evaluate Reverse Polish Notation

最新文章

热门文章