1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
// 150. Evaluate Reverse Polish Notation
#include "leetcode.h"
/*
* given an array of strings 'tokens' that represents an arithmetic expression
* in a reverse polish notation. evaluate the expression. return an integer that
* represents the value of the expression. note that the valid operators are + -
* * and /. each operand may be an integer or another expression. the division
* between two integers always truncates toward zero. there will not any
* division by zero. the input represents a valid arithmetic expression in
* reverse polish notation. the answer and all intermediate calculations can be
* represented in a 32 bit integer.
*/
int char_to_int(char *s) {
int len = strlen(s), res = 0;
bool pos = 1;
for (int i = 0; i < len; i++) {
if (s[i] == '-') {
pos = 0;
continue;
}
res *= 10 + s[i] - '0';
}
if (!pos)
res *= -1;
return res;
}
int evalRPN(char **tokens, int tokens_size) {
long long *stack = (long long *)malloc(tokens_size * sizeof(long long));
int idx = -1;
long long a, b;
for (int i = 0; i < tokens_size; i++) {
if (tokens[i][0] == '+') {
a = stack[idx];
idx--;
b = stack[idx];
stack[idx] = b + a;
} else if (strlen(tokens[i]) == 1 && tokens[i][0] == '-') {
a = stack[idx];
idx--;
b = stack[idx];
stack[idx] = b - a;
} else if (tokens[i][0] == '*') {
a = stack[idx];
idx--;
b = stack[idx];
stack[idx] = b * a;
} else if (tokens[i][0] == '/') {
a = stack[idx];
idx--;
b = stack[idx];
stack[idx] = b / a;
} else {
idx++;
stack[idx] = char_to_int(tokens[i]);
}
}
int ans = stack[0];
free(stack);
return ans;
}
int main() {
char t1[5][1] = {"2", "1", "+", "3", "*"};
char t2[5][2] = {"4", "13", "5", "/", "+"};
char t3[13][3] = {"10", "6", "9", "3", "+", "-11", "*",
"/", "*", "17", "+", "5", "+"};
printf("%d\n", evalRPN(t1, 5)); // expect: 9
printf("%d\n", evalRPN(t2, 5)); // expect: 6
printf("%d\n", evalRPN(t3, 13)); // expect: 22
}
|