Let's make this one less mysterious. For 224. Basic Calculator, the solution in this repository is mainly a stack solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: stack.
The notes already sitting in the source point us in the right direction:
- WA
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are print_stack, stack_contents, calculate, evaluateExpr.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA
02class Solution {
03public:
04 void print_stack(stack<char>& stk){
05 if(stk.empty()) return;
06 char* end = &stk.top() + 1;
07 char* begin = end - stk.size();
08 vector<char> stack_contents(begin, end);
09
10 cout << "stack: " << endl;
11 for(char e : stack_contents){
12 cout << e << " ";
13 }
14 cout << endl;
15 };
16
17 int calculate(string s) {
18 stack<char> oprs;
19 stack<int> opds;
20
21 char opr;
22 int opd = 0;
23
24 for(char c : s){
25 if(c == ' ') continue;
26 if(c >= '0' && c <= '9'){
27 opd = opd*10 + (c-'0');
28 // cout << "opd: " << opd << endl;
29 }else if(c == '('){
30 // cout << "push " << c << endl;
31 oprs.push(c);
32 }else if(c == ')'){
33 //evaluate the expression starts from last '('
34 bool popped = false;
35 while(!oprs.empty() && oprs.top() != ')'){
36 int last_opd = opds.top(); opds.pop();
37 char last_opr = oprs.top(); oprs.pop();
38 // cout << "last: " << last_opd << " " << last_opr << endl;
39 if(last_opr == '+'){
40 opd = last_opd + opd;
41 }else{
42 opd = last_opd - opd;
43 }
44 // print_stack(oprs);
45 if(!oprs.empty() && oprs.top() == '(' ){
46 if(!popped){
47 oprs.pop();
48 popped = true;
49 }else{
50 break;
51 }
52 }
53 }
54
55 // cout << "push " << opd << endl;
56 opds.push(opd);
57 opd = 0;
58 }else{
59 //c == '+' or '-'
60 if(opds.empty()){
61 //when we looked through "1+"
62 // cout << "push " << opd << " and " << c << endl;
63 opds.push(opd);
64 opd = 0;
65 oprs.push(c);
66 }else{
67 //when we looked through "1+2+"
68 //perform operation with last operand
69 // int last_opd = opds.top(); opds.pop();
70 // char last_opr = oprs.top(); oprs.pop();
71 // cout << "last: " << last_opd << " " << last_opr << endl;
72 // if(last_opr == '+'){
73 // opd = last_opd + opd;
74 // }else{
75 // opd = last_opd - opd;
76 // }
77 // print_stack(oprs);
78
79 if(opd != 0){
80 if(oprs.empty() || oprs.top() == '(' || oprs.top() == ')'){
81 // cout << "push " << opd << endl;
82 opds.push(opd);
83 opd = 0;
84 }
85
86 while(!oprs.empty() && oprs.top() != '(' && oprs.top() != ')'){
87 int last_opd = opds.top(); opds.pop();
88 char last_opr = oprs.top(); oprs.pop();
89 // cout << "last: " << last_opd << " " << last_opr << endl;
90 if(last_opr == '+'){
91 opd = last_opd + opd;
92 }else{
93 opd = last_opd - opd;
94 }
95 // cout << "push " << opd << endl;
96 opds.push(opd);
97 opd = 0;
98 // print_stack(oprs);
99 }
100 }
101
102 // cout << "push " << c << endl;
103 oprs.push(c);
104 }
105 }
106 }
107
108 int ans = 0;
109
110 //when we looked through "1+2+3"
111 if(!oprs.empty()){
112 int last_opd = opds.top(); opds.pop();
113 char last_opr = oprs.top(); oprs.pop();
114 if(last_opr == '+'){
115 ans = last_opd + opd;
116 }else{
117 ans = last_opd - opd;
118 }
119 // cout << "last: " << last_opd << " " << last_opr << ", ans: " << ans << endl;
120 }else if(!opds.empty()){
121 ans = opds.top(); opds.pop();
122 }else if(opd != 0){
123 ans = opd;
124 opd = 0;
125 }
126
127 return ans;
128 }
129};
130
131//Approach 1: Stack and String Reversal
132//Runtime: 40 ms, faster than 46.67% of C++ online submissions for Basic Calculator.
133//Memory Usage: 9.8 MB, less than 20.48% of C++ online submissions for Basic Calculator.
134//time: O(N), space: O(N)
135class Solution {
136public:
137 void print_stack(stack<char>& stk){
138 if(stk.empty()) return;
139 char* end = &stk.top() + 1;
140 char* begin = end - stk.size();
141 vector<char> stack_contents(begin, end);
142
143 cout << "oprs: " << endl;
144 for(char e : stack_contents){
145 cout << e << " ";
146 }
147 cout << endl;
148 };
149
150 void print_stack(stack<int>& stk){
151 if(stk.empty()) return;
152 int* end = &stk.top() + 1;
153 int* begin = end - stk.size();
154 vector<int> stack_contents(begin, end);
155
156 cout << "opds: " << endl;
157 for(int e : stack_contents){
158 cout << e << " ";
159 }
160 cout << endl;
161 };
162
163 int evaluateExpr(stack<int>& opds, stack<char>& oprs){
164 int res = 0;
165
166 //think about the case "(10)"
167 if(!opds.empty()){
168 res = opds.top(); opds.pop();
169 }
170
171 /*
172 recall that we push chars into stack in reverse order,
173 so here when we pop chars from stack,
174 they are in positive order
175
176 so ')' is the end of sub-expression
177 */
178 while(!opds.empty() && !oprs.empty() && oprs.top() != ')'){
179 //pop one operator and one operand at a time
180 char opr = oprs.top(); oprs.pop();
181
182 if(opr == '+'){
183 // cout << "+ " << opds.empty() << endl;
184 res += opds.top(); opds.pop();
185 }else{
186 // cout << "- " << opds.empty() << endl;
187 res -= opds.top(); opds.pop();
188 }
189 }
190
191 return res;
192 };
193
194 int calculate(string s) {
195 //cover the original expression with a set of parenthesis to avoid this extra call
196 s = '(' + s + ')';
197 reverse(s.begin(), s.end());
198
199 int opd = 0, p = 0;
200 stack<int> opds;
201 stack<char> oprs;
202
203 for(char c : s){
204 if(c == ' '){
205 continue;
206 }else if(c >= '0' && c <= '9'){
207 //c is a digit
208 opd = (c-'0')*pow(10, p) + opd;
209 ++p;
210 }else{
211 //meet +, -, or (), we first store the operand
212 if(p != 0){
213 // cout << "push " << opd << endl;
214 opds.push(opd);
215 opd = 0;
216 p = 0;
217 }
218
219 if(c == '('){
220 //the end of reversed sub-expression
221 // print_stack(oprs);
222 // print_stack(opds);
223 int res = evaluateExpr(opds, oprs);
224 // cout << "( " << oprs.empty() << endl;
225 oprs.pop(); //pop ')', the end of sub-expression
226 opds.push(res);
227 }else{
228 // cout << "push " << c << endl;
229 oprs.push(c);
230 }
231 }
232 }
233
234 return opds.top();
235 }
236};
237
238//Approach 2: Stack and No String Reversal(sign)
239//Runtime: 24 ms, faster than 76.53% of C++ online submissions for Basic Calculator.
240//Memory Usage: 8.1 MB, less than 54.22% of C++ online submissions for Basic Calculator.
241//time: O(N), space: O(N)
242class Solution {
243public:
244 int calculate(string s) {
245 stack<int> opds;
246 stack<int> signs;
247
248 int opd = 0;
249 int res = 0;
250 int sign = 1;
251
252 for(char c : s){
253 if(c >= '0' && c <= '9'){
254 opd = opd * 10 + (c-'0');
255 }else if(c == '+'){
256 // cout << res << " + " << sign << " * " << opd << endl;
257 res += sign * opd;
258 opd = 0;
259 sign = 1;
260 }else if(c == '-'){
261 // cout << res << " + " << sign << " * " << opd << endl;
262 // res "+" sign * opd here !!!
263 res += sign * opd;
264 opd = 0;
265 sign = -1;
266 }else if(c == '('){
267 /*
268 current res and sign is later used when we meet ')'
269 */
270 opds.push(res);
271 signs.push(sign);
272 // cout << "push " << res << " and " << sign << endl;
273 // cout << "opd: " << opd << endl;
274
275 /*
276 reset operand and result,
277 as if new evaluation begins for the new sub-expression
278 */
279 // opd = 0; //opd is already reset when we meet '+' or '-' before the '('
280 res = 0; //since res is already pushed into stack
281 sign = 1; //since sign is already pushed into stack
282 }else if(c == ')'){
283 // cout << res << " + " << sign << " * " << opd << endl;
284 res += sign * opd;
285 res *= signs.top(); signs.pop();
286 res += opds.top(); opds.pop();
287 // cout << "res: " << res << ", sign: " << sign << endl;
288 opd = 0; //already used
289 /*
290 after ')', we must meet '+' or '-',
291 and sign*opd is always 0, so res won't change
292
293 and we known that after '+' or '-',
294 opd and sign will be reset again,
295 so here we don't need to reset sign
296 */
297 // sign = 1;
298 }
299 }
300
301 // cout << res << " + " << sign << " * " << opd << endl;
302 return res + sign * opd;
303 }
304};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.