LeetCode笔记（5）Evaluate Reverse Polish Notation

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

这一题不是很难，关键是要理解逆波兰式。经典的算法是用Stack存储数字，每遇到一个符号就将栈顶的两个数字pop出来计算完后push回去。代码如下：

    int evalRPN(vector<string> &tokens) {
        vector<int> num;
        for (int i=0; i<tokens.size(); i++)
        {
            if (tokens[i].back() >= '0' && tokens[i].back() <= '9')
            {
                num.push_back(stoi(tokens[i]));
                continue;   
            }
            char c = tokens[i][0];
            int res;
            int rhs = num.back();
            num.pop_back();
            int lhs = num.back();
            num.pop_back();
            if (c == '+')
                res = lhs + rhs;
            else if (c == '-')
                res = lhs - rhs;
            else if (c == '*')
                res = lhs * rhs;
            else if (c == '/')
                res = lhs / rhs;
            num.push_back(res);
        }
        return num.front();
    }
};

问题在于，这一算法的思路从何而来呢？如果不是记住算法的话，从表达式本身得到这一计算并不是很直观。

实际上，这一算法做的事情是：从后序遍历的　逆波兰式表达式　得到　中序遍历　的　常见形式表达式，并计算值。中间隐含着构造了表达式的二叉树。也就是说，从逆波兰式表达式可以直接构造出代表他的二叉树。为了证明这一点，我显式实现了这一构造和计算过程：

struct Tnode{
    string val;
    Tnode * left;
    Tnode * right;
    Tnode(string x):val(x), left(NULL), right(NULL){}
};

class Solution {

    Tnode * constructTree(const vector<string> & tokens, int & cur)
    {
        Tnode * root = new Tnode(tokens[cur]);
        cur--;
        if (root->val.back()< '0' || root->val.front() > '9')
        {
            root->right = constructTree(tokens, cur);
            root->left = constructTree(tokens, cur);
        }
        return root;
    }

    int evalTree(Tnode * root)
    {
        if (root->val.back() >= '0' && root->val.back() <= '9')
            return stoi(root->val);

        char c = root->val[0];
        int res;
        int lhs = evalTree(root->left);
        int rhs = evalTree(root->right);
        if (c == '+')
            res = lhs + rhs;
        else if (c == '-')
            res = lhs - rhs;
        else if (c == '*')
            res = lhs * rhs;
        else if (c == '/')
            res = lhs / rhs;
        return res;
    }

public:
    int evalRPN(vector<string> &tokens) {
        int cur = tokens.size() - 1;
        return evalTree(constructTree(tokens, cur));
    }
};

这段code也能通过测试，甚至比上面的代码效率高5倍。

仔细观察这段代码，发现evalTree可以直接融合到constructTree中去，进一步可以省略掉tree结构的创建，直接计算值：

class Solution {

    int eval(const vector<string> & tokens, int & cur)
    {
        if (tokens[cur].back() >= '0' && tokens[cur].back() <= '9')
            return stoi(tokens[cur--]);

        char c = tokens[cur][0];
        cur--;
        int rhs = eval(tokens, cur);
        int lhs = eval(tokens, cur);

        if (c == '+')
            return lhs + rhs;
        else if (c == '-')
            return lhs - rhs;
        else if (c == '*')
            return lhs * rhs;
        else
            return lhs / rhs;
    }

public:
    int evalRPN(vector<string> &tokens) {
        int cur = tokens.size() - 1;
        return eval(tokens, cur);
    }
};

这样做的好处是不用显式使用stack，但是因为是递归，stack的空间和操作还是隐式进行了。

再反观最开始使用Stack的经典forwards算法，终于了解了它的实质：借用stack自底向上地构造二叉树并计算值，由于值计算出来后，树本身就没有用了，所以树的结构既不用显式构造也不用保存。

而最后不显式使用Stack的backwards算法则是自顶向下构建二叉树，再回溯计算。

这一题的经验：

从最开始看到这个算法后就记了下来，很快能写对，但是对其本身并不理解。又隐约记得逆波兰式和后序遍历的关系，一直觉得这个算法和Tree有某种关系。仔细研究下来，不仅理清了这一关系，还弄懂了经典的算法。一切都串了起来。
LeetCode OJ上，经典算法40ms, 第二个constructTree and evaluate的code 8ms，速度相差之大，而第三段code与第二段原理类似，时间却又恢复40ms。这中间的具体原因我仍然不确定，但是感觉与stack有关，当然也和具体的test data有关。如果有谁figure out了，麻烦告知。。

Leave a Reply Cancel reply