首页 > 数据结构 > 线性结构 > LeetCode-Evaluate Reverse Polish Notation[栈]
2014
11-19

LeetCode-Evaluate Reverse Polish Notation[栈]

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
分析

代码1

// LeetCode, Evaluate Reverse Polish Notation
// 递归,时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        int x, y;
        auto token = tokens.back();  tokens.pop_back();
        if (is_operator(token))  {
            y = evalRPN(tokens);
            x = evalRPN(tokens);
            if (token[0] == '+')       x += y;
            else if (token[0] == '-')  x -= y;
            else if (token[0] == '*')  x *= y;
            else                       x /= y;
        } else  {
            size_t i;
            x = stoi(token, &i);
        }
        return x;
    }
private:
    bool is_operator(const string &op) {
        return op.size() == 1 && string("+-*/").find(op) != string::npos;
    }
};

代码2

// LeetCode, Max Points on a Line
// 迭代,时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<string> s;
        for (auto token : tokens) {
            if (!is_operator(token)) {
                s.push(token);
            } else {
                int y = stoi(s.top());
                s.pop();
                int x = stoi(s.top());
                s.pop();
                if (token[0] == '+')       x += y;
                else if (token[0] == '-')  x -= y;
                else if (token[0] == '*')  x *= y;
                else                       x /= y;
                s.push(to_string(x));
            }
        }
        return stoi(s.top());
    }
private:
    bool is_operator(const string &op) {
        return op.size() == 1 && string("+-*/").find(op) != string::npos;
    }
};

Java代码:

public class Solution {
    public int evalRPN(String[] tokens) {
        int stack[] = new int[ tokens.length ];
        int len = 0;
        for(int i=0; i<tokens.length; i++){
            if(tokens[i].equals("+")){
                stack[len-2] = stack[len-2] + stack[len-1];
                len -= 1;
            }else if(tokens[i].equals("-")){
                stack[len-2] = stack[len-2] - stack[len-1];
                len -= 1;
            }
            else if(tokens[i].equals("*")){
                stack[len-2] = stack[len-2] * stack[len-1];
                len -= 1;
            }
            else if(tokens[i].equals("/")){
                stack[len-2] = stack[len-2] / stack[len-1];
                len -= 1;
            }else
               stack[len++] = Integer.parseInt( tokens[i] ); 
        }
        return stack[0];
    }
}

  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。