文章目录
  1. 1. Basic Calculator
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

Basic Calculator

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

思路

转换成后缀表达式,再进行计算。

解题

c++版

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
int calculate(string s) {
vector<long> postfix = to_postfix(s);
int len = postfix.size();
if (len == 0) {
return 0;
}
vector<long> tmp;
long a, b;
for (int i=0; i<len; i++) {
long ch = postfix[i];
switch(ch) {
case '+':
a = tmp.back();
tmp.pop_back();
tmp.back() = tmp.back() + a;
break;
case '-':
a = tmp.back();
tmp.pop_back();
tmp.back() = tmp.back() - a;
break;
default:
tmp.push_back(-ch);
}
}
return tmp[0];
}

vector<long> to_postfix(const string& s) {
int len = s.size();
// operators
vector<char> operato;
// generated postfix experssion of this infix experssion
vector<long> postfix;

int val = 0;
bool innum = false;

for (int i=0; i<len; i++) {
char ch = s[i];
switch (ch) {
case ' ':
// skip space
continue;
case '-':
case '+':
while (!operato.empty() && operato.back() != '(') {
postfix.push_back(operato.back());
operato.pop_back();
}
operato.push_back(ch);
break;
case '(':
// just push to operato
operato.push_back(ch);
break;
case ')':
// move any operato between this ')' and it's paired '('
while (!operato.empty() && operato.back() != '(') {
postfix.push_back(operato.back());
operato.pop_back();
}
// destroy '(' placeholder
operato.pop_back();
break;
default:
if (innum) {
val = val * 10 + ch - '0';
} else {
val = ch - '0';
innum = true;
}
// look ahead
if (i+1 == len || s[i+1] > '9' || s[i+1] < '0') {
postfix.push_back(-val);
innum = false;
}
}
}

while (!operato.empty()) {
postfix.push_back(operato.back());
operato.pop_back();
}
return postfix;
}
};

python版

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
class Solution:
# @param {string} s
# @return {integer}
def calculate(self, s):
tokens = self.toRPN(s)
return self.evalRPN(tokens)

operators = ['+', '-', '*', '/']
def toRPN(self, s):
tokens, stack = [], []
number = ''
for c in s:
if c.isdigit():
number += c
else:
if number:
tokens.append(number)
number = ''
if c in self.operators:
while len(stack) and self.getPriority(stack[-1]) >= self.getPriority(c):
tokens.append(stack.pop())
stack.append(c)
elif c == '(':
stack.append(c)
elif c == ')':
while len(stack) and stack[-1] != '(':
tokens.append(stack.pop())
stack.pop()
if number:
tokens.append(number)
while len(stack):
tokens.append(stack.pop())
return tokens

def evalRPN(self, tokens):
operands = []
for token in tokens:
if token in self.operators:
y, x = operands.pop(), operands.pop()
operands.append(self.getVal(x, y, token))
else:
operands.append(int(token))
return operands[0]

def getVal(self, x, y, operator):
return {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: int(float(x) / y),
}[operator](x, y)

def getPriority(self, operator):
return {
'+' : 1,
'-' : 1,
'*' : 2,
'/' : 2,
}.get(operator, 0)

文章目录
  1. 1. Basic Calculator
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题