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


// 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;
}
};


// 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. 旅游大巴倒车，后面隧道出来的货车（装大理石）的，一头撞了上去，然后发生了图片二的场景，图片二开始的后买你几个站着的人其实就是给司机望风的。货车司机当场死亡，事故判定旅游车司机全责，判刑。这个事件告诉我们特么高速公路就不能是一个道的么？！什么事故都不会发生

2. 旅游大巴倒车，后面隧道出来的货车（装大理石）的，一头撞了上去，然后发生了图片二的场景，图片二开始的后买你几个站着的人其实就是给司机望风的。货车司机当场死亡，事故判定旅游车司机全责，判刑。这个事件告诉我们特么高速公路就不能是一个道的么？！什么事故都不会发生

3. 旅游大巴倒车，后面隧道出来的货车（装大理石）的，一头撞了上去，然后发生了图片二的场景，图片二开始的后买你几个站着的人其实就是给司机望风的。货车司机当场死亡，事故判定旅游车司机全责，判刑。这个事件告诉我们特么高速公路就不能是一个道的么？！什么事故都不会发生

4. 旅游大巴倒车，后面隧道出来的货车（装大理石）的，一头撞了上去，然后发生了图片二的场景，图片二开始的后买你几个站着的人其实就是给司机望风的。货车司机当场死亡，事故判定旅游车司机全责，判刑。这个事件告诉我们特么高速公路就不能是一个道的么？！什么事故都不会发生

5. 旅游大巴倒车，后面隧道出来的货车（装大理石）的，一头撞了上去，然后发生了图片二的场景，图片二开始的后买你几个站着的人其实就是给司机望风的。货车司机当场死亡，事故判定旅游车司机全责，判刑。这个事件告诉我们特么高速公路就不能是一个道的么？！什么事故都不会发生

6. 漂亮。佩服。
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));
}
}

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