These are the notes for C++ Coding Questions, episode 16, placement practice for people who finished the SyntaxPilot C++ course. One data structure, three classic questions: balanced brackets (why counting fails, and the empty-stack crash), the next greater element with a monotonic stack (from O(n²) to O(n), and a default of 0 that should be -1), and evaluating a postfix expression (the first pop is the right-hand number, and multi-digit numbers need whole tokens).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| A pile of plates: you only touch the top one | a stack: push, top, pop, last in first out |
| Packing a suitcase: open the suitcase, a bag, a pouch; zip the pouch first | brackets: the newest open bracket must close first |
| Zipping something you never opened | a closer when the stack is empty |
| People in a line for a photo, each looking right for the first taller person | the next greater element |
| People still waiting stand on a pile; a tall person arrives and answers everyone shorter on top | a monotonic stack of indexes |
| A shopkeeper's pile of chits: an operator chit takes the top two, the top one is the right-hand number | postfix evaluation: pop b first, then a |
A stack in one minute: std::stack
A stack is a container where you only touch the top. The last value pushed is the first one out: LIFO (last in, first out).
#include <stack>
stack<char> st;
st.push('('); // put on top
st.top(); // read the top (does not remove it)
st.pop(); // remove the top (returns nothing)
st.empty(); // true if there is nothing in it
st.size(); // how many values
push,top,pop,emptyandsizeare all O(1).pop()returns nothing: readtop()first, thenpop().top()orpop()on an empty stack is undefined behaviour (UB): the C++ standard says nothing about what happens. In the video it crashed; on another machine it could silently read garbage.
Q1: Balanced brackets
Problem. For each word made of ( ) [ ] { }, print YES if every bracket is closed by the same kind, in the right order, else NO.
| Input | Output | Why |
|---|---|---|
{[()]} |
YES |
closed in reverse order |
()[]{} |
YES |
side by side |
([)] |
NO |
) closes while [ is still open |
(( |
NO |
opens left over |
()) |
NO |
a closer with nothing open |
Think out loud. Three edge cases: the wrong order, opens left over at the end, and a closer with nothing open.
The obvious attempt: count each kind
#include <iostream>
#include <string>
using namespace std;
bool balanced(const string& s) {
int round = 0, square = 0, curly = 0;
for (char c : s) {
if (c == '(') round++;
if (c == ')') round--;
if (c == '[') square++;
if (c == ']') square--;
if (c == '{') curly++;
if (c == '}') curly--;
if (round < 0 || square < 0 || curly < 0) return false;
}
return round == 0 && square == 0 && curly == 0;
}
int main() {
string s;
while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
return 0;
}
On {[()]} ()[]{}:
{[()]}: YES
()[]{}: YES
On {[()]} ([)]:
{[()]}: YES
([)]: YES
([)] says YES. Each counter goes up once and down once, so all three end at zero, but the round bracket was closed while the square one inside it was still open. Counts can't see the order.
Why a stack
When a closer comes, it must match the newest bracket that is still open. "Remember things in order and always look at the newest" is exactly a stack: push every open bracket; on a closer, top() must be its partner, then pop().
Attempt: a stack, without the empty check
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool balanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
char open = st.top();
st.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') ||
(c == '}' && open != '{')) return false;
}
}
return st.empty();
}
int main() {
string s;
while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
return 0;
}
On {[()]} ([)] it is right:
{[()]}: YES
([)]: NO
On {[()]} ([)] (( ()) the compiler shows the lines printed so far and then:
{[()]}: YES
([)]: NO
((: NO
Runtime Error (SIGSEGV)
SIGSEGV (segmentation fault) means the program touched memory it doesn't own. In ()), the first ) pops the (; the second ) calls st.top() on an empty stack.
Fix: check st.empty() before top()
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool balanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
if (st.empty()) return false; // a closer with nothing open
char open = st.top();
st.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') ||
(c == '}' && open != '{')) return false;
}
}
return st.empty();
}
int main() {
string s;
while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
return 0;
}
{[()]}: YES
([)]: NO
((: NO
()): NO
The last line, return st.empty();, catches opens left over (((). O(n) time (each bracket pushed and popped at most once), O(n) space (a word of only open brackets).
Q2: Next greater element
Problem. For each number, print the first larger number to its right, or -1 if there is none.
| Input | Output |
|---|---|
4 5 2 25 |
5 25 25 -1 |
13 7 6 12 10 15 3 |
15 12 12 15 15 -1 -1 |
Think out loud. The last number always gets -1; falling numbers get -1 everywhere. Big test: 500,000 falling prices (when n is 0, the program builds 500000 499999 ... 1).
The obvious attempt: scan to the right
#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[j] > a[i]) { ans[i] = a[j]; break; }
return ans;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 falling prices
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
vector<int> ans = nextGreater(a);
if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
for (int x : ans) cout << x << " ";
cout << "\n";
return 0;
}
On 4 5 2 25:
5 25 25 -1
On the big test:
Time Limit Exceeded
Nobody finds a larger number, so every scan runs to the end: about n²/2 = 125,000,000,000 comparisons. Each scan starts from scratch and forgets what the earlier scans saw.
Why the pile works: a monotonic stack
Keep the indexes still waiting for an answer on a stack. When a[i] arrives, it is the answer for every waiting index whose value is smaller: pop them and fill in ans. Then push i.
13 7 6 12: stack 13 7 6 → 12 arrives: 6 gets 12, 7 gets 12, 13 keeps waiting
stack 13 12
The values on the stack always fall from bottom to top: that's a monotonic stack (a stack kept in sorted order). We store indexes, not values, so we know whose answer to fill in. Each index is pushed once and popped at most once: O(n).
Attempt: the monotonic stack with vector<int> ans(n)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> ans(n);
stack<int> st; // indexes still waiting
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i]; // a[i] answers everyone smaller
st.pop();
}
st.push(i);
}
return ans;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 falling prices
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
vector<int> ans = nextGreater(a);
if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
for (int x : ans) cout << x << " ";
cout << "\n";
return 0;
}
5 25 25 0
The last answer is 0, not -1. vector<int> ans(n) fills every slot with 0; indexes left on the stack at the end are never answered, so they keep the 0.
Fix: vector<int> ans(n, -1)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1); // nobody answered yet
stack<int> st; // indexes still waiting
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i]; // a[i] answers everyone smaller
st.pop();
}
st.push(i);
}
return ans;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 falling prices
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
vector<int> ans = nextGreater(a);
if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
for (int x : ans) cout << x << " ";
cout << "\n";
return 0;
}
On 13 7 6 12 10 15 3:
15 12 12 15 15 -1 -1
On the big test (500,000 falling prices), instantly:
last: -1
O(n) time, O(n) space (the stack and the answers).
Q3: Evaluate a postfix expression
Postfix (also called Reverse Polish notation) writes the operator after its two numbers: 2 3 + means 2 + 3. It needs no brackets: 2 3 1 * + 9 - means (2 + 3 × 1) − 9. A token is one piece of the expression: a number or an operator.
Problem. Each line is a postfix expression with tokens separated by spaces. Print its value.
| Input | Output |
|---|---|
2 3 + |
5 |
2 3 1 * + 9 - |
-4 |
10 2 / |
5 |
100 20 30 + - |
50 |
Think out loud. Numbers go on a stack; an operator takes the top two, combines them, and pushes the result. Edge cases: - and / care about the order; numbers can have more than one digit.
The obvious attempt: pop a, then b
#include <iostream>
#include <string>
#include <stack>
using namespace std;
long long evalPostfix(const string& e) {
stack<long long> st;
for (char c : e) {
if (c == ' ') continue;
if (isdigit(c)) { st.push(c - '0'); continue; }
long long a = st.top(); st.pop();
long long b = st.top(); st.pop();
if (c == '+') st.push(a + b);
if (c == '-') st.push(a - b);
if (c == '*') st.push(a * b);
if (c == '/') st.push(a / b);
}
return st.top();
}
int main() {
string line;
while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
return 0;
}
2 3 + = 5
2 3 1 * + 9 - = 4
4, but the answer is -4. At the -, the stack is 5 9 with 9 on top. We popped 9 into a, 5 into b, and computed 9 − 5.
Why: the first pop is the RIGHT operand
9 was pushed last, so it comes out first: it is the right-hand side. + and * don't care about the order, so they hid the bug; - and / do. Pop b (right) first, then a (left), and push a - b.
Attempt: the right order, still char by char
#include <iostream>
#include <string>
#include <stack>
using namespace std;
long long evalPostfix(const string& e) {
stack<long long> st;
for (char c : e) {
if (c == ' ') continue;
if (isdigit(c)) { st.push(c - '0'); continue; }
long long b = st.top(); st.pop(); // the TOP is the right side
long long a = st.top(); st.pop();
if (c == '+') st.push(a + b);
if (c == '-') st.push(a - b);
if (c == '*') st.push(a * b);
if (c == '/') st.push(a / b);
}
return st.top();
}
int main() {
string line;
while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
return 0;
}
2 3 + = 5
2 3 1 * + 9 - = -4
10 2 / = 0
10 2 / says 0. Character by character, 10 became two numbers, 1 and 0; then / computed 0 / 2.
Fix: read whole tokens with stringstream
A stringstream (from <sstream>) reads a string the way cin reads the keyboard: in >> tok gives one space-separated token at a time. stoll (string to long long) turns "10" into 10.
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
using namespace std;
long long evalPostfix(const string& e) {
stack<long long> st;
stringstream in(e);
string tok;
while (in >> tok) { // one whole token at a time
if (isdigit(tok[0])) { st.push(stoll(tok)); continue; }
long long b = st.top(); st.pop(); // the TOP is the right side
long long a = st.top(); st.pop();
if (tok == "+") st.push(a + b);
if (tok == "-") st.push(a - b);
if (tok == "*") st.push(a * b);
if (tok == "/") st.push(a / b);
}
return st.top();
}
int main() {
string line;
while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
return 0;
}
2 3 + = 5
2 3 1 * + 9 - = -4
10 2 / = 5
100 20 30 + - = 50
O(n) time (each token is pushed or popped a fixed number of times), O(n) space. A real calculator would also reject division by zero and a malformed expression (too few numbers on the stack); see the practice questions.
When is a stack the right tool?
- When the newest unfinished thing is the one that matters next.
- Brackets: the newest open bracket. Next greater: the newest index still waiting. Postfix: the two newest numbers.
- Everyday stacks: undo in an editor, the browser's back button, the call stack of your program's functions.
- Before every
top()orpop(), ask: can the stack be empty here?
| Question | What the stack holds | Pops when |
|---|---|---|
| balanced brackets | open brackets | a closer arrives |
| next greater | indexes still waiting | a larger value arrives |
| postfix | numbers | an operator arrives |
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| brackets, counters | O(n) but wrong | O(1) |
| brackets, stack | O(n) | O(n) |
| next greater, scan right | O(n²): TLE for 500,000 | O(1) |
| next greater, monotonic stack | O(n) | O(n) |
| postfix, stack of numbers | O(n) | O(n) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| counting each bracket type | ([)]: YES |
counts can't see the order | a stack of open brackets |
st.top() with no check |
Runtime Error (SIGSEGV) on ()) |
top() of an empty stack (UB) |
if (st.empty()) return false; |
forgetting return st.empty(); |
((: YES |
opens left over | the stack must end empty |
| scanning right for every element | Time Limit Exceeded | O(n²) | a monotonic stack |
vector<int> ans(n) |
5 25 25 0 |
unanswered slots keep 0 | vector<int> ans(n, -1) |
| pushing values instead of indexes | can't tell whose answer to fill | values aren't positions | push i, read a[st.top()] |
pop a first, then b |
2 3 1 * + 9 - = 4 |
the top is the right side | pop b first, then a |
| reading char by char | 10 2 / = 0 |
10 read as 1 and 0 |
stringstream + stoll |
st.pop() used as a value |
error: void value not ignored as it ought to be |
pop() returns void |
x = st.top(); st.pop(); |
The last one is a compile error; for example int x = st.pop(); gives:
main.cpp: In function 'int main()':
main.cpp:7:19: error: void value not ignored as it ought to be
7 | int x = st.pop();
| ~~~~~~^~
Your turn: a stack that knows its minimum (solution)
Problem. Commands push x, pop, min. Every operation, min included, in O(1).
Idea. A second stack holds, at each level, the minimum of everything at or below that level. Push: mins.push(min(x, mins.top())). Pop: pop both.
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct MinStack {
stack<int> vals, mins; // mins.top() = minimum of vals
void push(int x) {
vals.push(x);
mins.push(mins.empty() ? x : min(x, mins.top()));
}
void pop() { vals.pop(); mins.pop(); }
int getMin() const { return mins.top(); }
bool empty() const { return vals.empty(); }
};
int main() {
MinStack s;
string op;
while (cin >> op) {
if (op == "push") { int x; cin >> x; s.push(x); }
else if (op == "pop") { if (!s.empty()) s.pop(); }
else cout << (s.empty() ? string("empty") : to_string(s.getMin())) << "\n";
}
return 0;
}
Input push 5 push 3 push 7 min pop pop min pop min:
3
5
empty
Practice questions (with solutions)
1. Previous smaller element. For each number, print the nearest smaller number to its left, or -1.
Solution
A monotonic stack again, read left to right: pop everything that is not smaller than a[i]; whatever is left on top is the answer; then push a[i].
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
stack<int> st; // values, rising from bottom to top
for (int x : a) {
while (!st.empty() && st.top() >= x) st.pop();
cout << (st.empty() ? -1 : st.top()) << " ";
st.push(x);
}
cout << "\n";
return 0;
}
Input 6 / 4 5 2 10 8 9:
-1 4 -1 2 2 8
2. Stock span. For each day, how many days in a row ending today had a price at most today's price?
Solution
Keep indexes of days with a higher price on a stack. Pop the days with price ≤ today; the span is i − (index on top), or i + 1 if the stack is empty.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int& x : p) cin >> x;
stack<int> st; // indexes of higher prices
for (int i = 0; i < n; i++) {
while (!st.empty() && p[st.top()] <= p[i]) st.pop();
cout << (st.empty() ? i + 1 : i - st.top()) << " ";
st.push(i);
}
cout << "\n";
return 0;
}
Input 7 / 100 80 60 70 60 75 85:
1 1 1 2 1 4 6
3. Reverse a string with a stack.
Solution
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
string s;
while (cin >> s) {
stack<char> st;
for (char c : s) st.push(c);
string r;
while (!st.empty()) { r += st.top(); st.pop(); }
cout << r << "\n";
}
return 0;
}
Input stack syntaxpilot:
kcats
tolipxatnys
(std::reverse does the same in place; the stack shows LIFO at work.)
4. A safe postfix calculator. Print error for division by zero or a malformed expression.
Solution
Check that two numbers are on the stack before every operator, that b != 0 before /, and that exactly one number is left at the end.
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
using namespace std;
bool evalSafe(const string& e, long long& result) {
stack<long long> st;
stringstream in(e);
string tok;
while (in >> tok) {
if (isdigit(tok[0])) { st.push(stoll(tok)); continue; }
if (st.size() < 2) return false; // not enough numbers
long long b = st.top(); st.pop();
long long a = st.top(); st.pop();
if (tok == "+") st.push(a + b);
else if (tok == "-") st.push(a - b);
else if (tok == "*") st.push(a * b);
else if (tok == "/") { if (b == 0) return false; st.push(a / b); }
else return false; // unknown token
}
if (st.size() != 1) return false;
result = st.top();
return true;
}
int main() {
string line;
while (getline(cin, line)) {
long long r;
if (evalSafe(line, r)) cout << line << " = " << r << "\n";
else cout << line << " = error\n";
}
return 0;
}
2 3 1 * + 9 - = -4
4 0 / = error
1 + = error
1 2 = error
Mini project: an undo button for a text box
Commands: type <word> adds a word, undo removes the last change, show prints the text. Every change goes on a stack; undo pops it. This is how editors implement undo.
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
string text, cmd;
stack<string> history; // the text before each change
while (cin >> cmd) {
if (cmd == "type") {
string w;
cin >> w;
history.push(text);
text += (text.empty() ? "" : " ") + w;
} else if (cmd == "undo") {
if (history.empty()) { cout << "(nothing to undo)\n"; continue; }
text = history.top();
history.pop();
} else cout << "[" << text << "]\n";
}
return 0;
}
[hello stack world]
[hello stack]
[]
(nothing to undo)
Quick quiz
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> st;
for (int x : {3, 1, 4, 1, 5}) {
while (!st.empty() && st.top() > x) st.pop();
st.push(x);
}
cout << st.size() << " " << st.top() << "\n";
return 0;
}
(A) 3 5 (B) 5 5 (C) 2 5 (D) 3 4
Answer
(A) 3 5. 3 → [3]; 1 pops 3 → [1]; 4 → [1 4]; 1 pops 4 → [1 1]; 5 → [1 1 5]. Size 3, top 5.
3 5
Interview questions
- What is a stack, and what are its operations' costs? A LIFO container:
push,pop,top,empty,size, all O(1). - Why can't counters check brackets? They lose the order:
([)]has balanced counts but closes in the wrong order. - What happens on
top()of an emptystd::stack? Undefined behaviour: a crash, garbage, or anything. Always checkempty()first. - What is a monotonic stack? A stack kept in sorted order by popping elements that break the order before each push; used for next/previous greater or smaller.
- Why is the monotonic stack O(n) with a
whileinside afor? Each index is pushed once and popped at most once: at most 2n operations in total. - Why store indexes on the stack? To know which answer slot to fill, and to compute distances (stock span).
- In postfix, which operand is popped first? The right one:
a b -popsb, thena, computesa - b. - Why is postfix easy for computers? No brackets and no precedence rules: one left-to-right pass with a stack.
- What does
std::stackuse underneath? Astd::dequeby default;stack<int, vector<int>>uses a vector. - How do you make a min-stack? A second stack holding the running minimum at each level.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Stack | A container where you only add, read and remove at the top | a pile of plates |
| LIFO | Last in, first out | the last plate on is the first off |
push / pop / top |
Add on top / remove the top / read the top | st.push('(') |
std::stack |
The C++ stack adaptor, from <stack> |
stack<char> st; |
| Empty stack | A stack with no values; top()/pop() on it is UB |
st.empty() is true |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to: anything may happen | top() of an empty stack |
SIGSEGV |
Segmentation fault: the program touched memory it doesn't own | Runtime Error (SIGSEGV) |
| Balanced brackets | Every bracket closed by the same kind in reverse order | {[()]} |
| Next greater element | The first larger value to the right | 5 for 4 in 4 5 2 25 |
| Monotonic stack | A stack whose values stay sorted, by popping before each push | values fall from bottom to top |
| Postfix (Reverse Polish) | Operators written after their operands | 2 3 + = 5 |
| Operand | A value an operator works on | 2 and 3 in 2 3 + |
| Token | One piece of an expression: a number or an operator | 10, / |
stringstream |
A stream that reads from or writes to a string, from <sstream> |
stringstream in(e); in >> tok; |
stoll |
String to long long | stoll("10") is 10 |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | O(n²) on 500,000 numbers |
Summary
- Stack: only the top;
push,top,pop,emptyare O(1);pop()returns nothing; nevertop()/pop()an empty stack. - Balanced brackets: push opens; on a closer the stack must be non-empty and its top the partner; end with an empty stack. O(n).
- Next greater element: a monotonic stack of indexes; a larger value answers everyone smaller on top; default
-1. O(n). - Postfix: numbers on a stack; an operator pops
b(right) thena(left); read whole tokens withstringstream. O(n).
Next episode: Queue and deque questions: a queue using two stacks (amortised O(1)), the sliding window maximum with a deque, and the first non-repeating character in a stream.