-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathBasic Calculator II
More file actions
148 lines (136 loc) · 4.28 KB
/
Basic Calculator II
File metadata and controls
148 lines (136 loc) · 4.28 KB
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/******************************************************************
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
*************************************************************************/
class Solution {
public:
int calculate(string s) {
int n = s.size();
stack<int> num_stack;
stack<char> sign_stack;
int num, sum=0;
num = 0;
for(int i = 0;i<n;i++)
{
if(s[i]==' ')continue;
if(s[i]>='0' && s[i]<='9')
num = num*10+s[i]-'0';
else if(s[i]=='+' || s[i]=='-'||s[i]=='*'||s[i]=='/')
{
if(!sign_stack.empty()&&(sign_stack.top()=='*' || sign_stack.top()=='/'))
{
char sign = sign_stack.top();
sign_stack.pop();
int pre_num = num_stack.top();
num_stack.pop();
if(sign == '*') num_stack.push(pre_num*num);
if(sign == '/') num_stack.push(pre_num/num);
sign_stack.push(s[i]);
}
else
{
num_stack.push(num);
sign_stack.push(s[i]);
}
num = 0;
}
}
//hanle the last number.
if(!sign_stack.empty() && (sign_stack.top()=='*' || sign_stack.top()=='/'))
{
char sign = sign_stack.top();
sign_stack.pop();
int pre_num = num_stack.top();
num_stack.pop();
if(sign == '*') num_stack.push(pre_num*num);
if(sign == '/') num_stack.push(pre_num/num);
}
else
num_stack.push(num);
//compute the sum value
while(!num_stack.empty())
{
int tmp_num = num_stack.top();
if(!sign_stack.empty())
{
char sign = sign_stack.top();
sign_stack.pop();
if(sign == '+') sum = sum+tmp_num;
if(sign == '-') sum = sum-tmp_num;
}
else
sum = sum + tmp_num;
num_stack.pop();
}
return sum;
}
};
/** C++ solution with queue **************
* class Solution {
public:
int calculate(string s) {
queue<int> numq;
queue<char> signq;
int todo_num;
char todo_sign = 0;
char sign;
int num = 0;
int n1, n2;
for(char c : s)
{
if(isdigit(c))
{
num = num*10 + c - '0';
}
else if(c == '+' || c == '-')
{
if(todo_sign != 0)
{
if(todo_sign == '*')
num = todo_num * num;
else if(todo_sign == '/')
num = todo_num / num;
todo_sign = 0;
}
numq.push(num); num = 0;
signq.push(c);
}
else if(c == '*' || c == '/')
{
if(todo_sign == '*')
todo_num = todo_num * num;
else if(todo_sign == '/')
todo_num = todo_num / num;
else
todo_num = num;
todo_sign = c;
num = 0;
}
}
if(todo_sign == '*')
num = todo_num*num;
if(todo_sign == '/')
num = todo_num / num;
numq.push(num);
n1 = numq.front(); numq.pop();
while(signq.size() > 0)
{
sign = signq.front(); signq.pop();
n2 = numq.front(); numq.pop();
if(sign == '+')
n1 = n1 + n2;
else if(sign == '-')
n1 = n1 - n2;
}
return n1;
}
};
********************/