Source: COP 3502C Coding Problems (Stacks & Queues)
Tags: palindrome check, balanced parentheses, bracket matching, infix to postfix, reverse Polish notation, postfix evaluation, stack applications, queue applications, COP 3502C, Computer Science I, UCF, C programming
Difficulty: Intermediate Prerequisites: You need to be comfortable implementing a stack (push/pop) and a queue (enqueue/dequeue) in C. See Part 1 of these notes if those feel uncertain. Familiarity with strlen, strtok, and basic string handling in C is also assumed.
Once you can build a stack and a queue, the next step is using them to solve real problems. This section covers five classic applications that appear regularly on COP 3502C exams: palindrome detection, word reversal, balanced-parentheses checking, infix-to-postfix conversion, and postfix expression evaluation. Each one demonstrates a different reason you would reach for a stack or a queue, and together they form the core "applied" portion of this unit.
Stacks are useful whenever you need to reverse something or match things that nest (characters for palindromes, brackets for balancing, operators for notation conversion). Queues are useful when you need to preserve the original order while restructuring. These five problems are the patterns that exam questions are built from.
Palindrome
A string that reads the same forwards and backwards, such as "racecar" or "madam". Think of it as: spell it backwards, and you get the same word.
Balanced parentheses
A string where every opening bracket ( (, [, { ) has a corresponding closing bracket of the same type, in the correct nesting order. In simple terms, every opener finds its closer, and they do not interleave incorrectly.
Infix notation
The standard way humans write arithmetic: operator between operands, e.g. 3 + 4.
Postfix notation (reverse Polish notation, RPN)
A notation where the operator follows its operands, e.g. 3 4 +. No parentheses are needed because the order of operations is unambiguous.
Operator precedence
The rule that * and / bind more tightly than + and -. In infix-to-postfix conversion, higher-precedence operators on the stack get popped before lower-precedence ones are pushed.
Shunting-yard algorithm
Dijkstra's algorithm for converting infix to postfix using a stack. The name comes from the way operators are "shunted" between input, stack, and output, like railway cars in a shunting yard.
The idea is straightforward: push every character of the string onto a stack, then pop them off one by one and compare to the original string. Because a stack reverses order, if the string is a palindrome the reversed sequence will match.
The stack stores char values instead of int.
Push each character from index 0 to len - 1.
Pop each character and compare to str[i] for the same range. If any mismatch occurs, return 0 (false). If all match, return 1 (true).
int is_palindrome(char *str) {
stack s;
s.top = -1;
int len = strlen(str);
for (int i = 0; i < len; i++)
push(&s, str[i]);
for (int i = 0; i < len; i++) {
char c = pop(&s);
if (c != str[i]) return 0;
}
return 1;
}
This approach uses O(n) extra space for the stack. A more space-efficient method would compare characters from both ends towards the middle, but the stack-based version is what the exam expects you to know.
To reverse the order of words (not characters) in a string, you can tokenise the string with strtok, enqueue each word, then dequeue them to reconstruct.
strtok(str, " ") splits on spaces, returning one token at a time.
Each token (a pointer into the original string) gets enqueued.
After all tokens are enqueued, dequeue them and concatenate with spaces.
A note on the source code: the provided solution enqueues in order and dequeues in order, which actually preserves word order rather than reversing it. A true reversal would use a stack instead, or dequeue into an intermediate structure and reverse. This is worth being aware of if the exam asks you to critique code. The underlying mechanics (tokenise, store, reconstruct) remain the important pattern.
This is one of the most commonly tested stack applications. The algorithm:
Walk through the string character by character.
If you encounter an opening bracket ( (, [, { ), push it.
If you encounter a closing bracket ( ), ], } ), pop from the stack and check whether the popped character is the matching opener. If it does not match, or if the stack is empty when you try to pop, the parentheses are unbalanced.
After processing the entire string, check that the stack is empty. Leftover openers mean there are unmatched opening brackets.
int is_balanced(char *str) {
stack s;
s.top = -1;
int len = strlen(str);
for (int i = 0; i < len; i++) {
char c = str[i];
if (c == '(' || c == '[' || c == '{')
push(&s, c);
else if (c == ')' || c == ']' || c == '}') {
char x = pop(&s);
if (c == ')' && x != '(') return 0;
if (c == ']' && x != '[') return 0;
if (c == '}' && x != '{') return 0;
}
}
return s.top == -1;
}
The final return s.top == -1 catches the case where extra opening brackets remain.
This converts expressions like 3 + 4 2 into 3 4 2 +. The stack holds operators, and the output accumulates operands and operators in postfix order.
The full algorithm:
Read each token. If it is an operand (number or variable), append it directly to the output.
If it is an operator, pop operators from the stack and append them to the output as long as the operator on top of the stack has greater or equal precedence. Then push the current operator.
If it is (, push it.
If it is ), pop and append until you reach the matching (, then discard the (.
After all tokens are read, pop and append any remaining operators.
The precedence function assigns 2 to * and /, and 1 to + and -.
Note: the Python pseudocode in the source material is simplified and does not handle precedence correctly (it pops all operators when it hits any operand). The full shunting-yard algorithm described above is what you should study for the exam.
Given a postfix string like 5 3 + 2 *, evaluate it to produce a numerical result (16 in this case).
Read each token. If it is an operand, push it onto the stack.
If it is an operator, pop two operands. Apply the operator. Push the result.
After processing all tokens, the stack contains exactly one value: the answer.
Input: 5 3 + 2 *
Step 1: push 5 → stack: [5]
Step 2: push 3 → stack: [5, 3]
Step 3: pop 3, pop 5, compute 5+3=8, push 8 → stack: [8]
Step 4: push 2 → stack: [8, 2]
Step 5: pop 2, pop 8, compute 8*2=16, push 16 → stack: [16]
Result: 16
Pay attention to the order of the operands when popping. The first value popped is the right operand, the second is the left operand. For addition and multiplication this does not matter (commutative), but for subtraction and division the order is critical: operand2 - operand1 and operand2 / operand1.
Precedence table for arithmetic operators:
Operator | Precedence |
|---|---|
| 2 (higher) |
| 1 (lower) |
Bracket matching pairs:
Opener | Closer |
|---|---|
|
|
|
|
|
|
Balanced-parentheses checking is exactly what compilers and code editors do to validate syntax. Every time your IDE highlights a mismatched bracket, it is running a variant of this algorithm. Postfix evaluation is how many calculators (particularly HP calculators) and stack-based virtual machines process arithmetic. Infix-to-postfix conversion is a core step in compiler design when translating human-readable expressions into machine-executable instructions.
Students often forget to check s.top == -1 at the end of is_balanced. Without this check, a string like "(((" would incorrectly pass as balanced because no mismatch was ever triggered.
In postfix evaluation, students frequently swap the operand order. When you pop twice, the first pop gives the right operand and the second gives the left. Writing operand1 - operand2 instead of operand2 - operand1 will give you the wrong sign.
Students sometimes assume infix-to-postfix conversion just moves operators to the end. Precedence and associativity matter. 3 + 4 2 becomes 3 4 2 +, not 3 4 + 2 *.
The palindrome check in the source material is case-sensitive and includes spaces. On an exam, read the problem carefully to see whether you should normalise the input first.
⚠️ Balanced parentheses is one of the most frequently tested stack problems in CS1 exams. Be able to trace through an example string by hand, showing the stack state at each step.
⚠️ Know how to evaluate a postfix expression by hand. Exam questions often give you a postfix string and ask for the numerical result, step by step.
⚠️ Understand why a stack reverses order (LIFO) and how that property is exploited in palindrome checking and infix-to-postfix conversion.
⚠️ Be prepared to write is_balanced or is_palindrome from memory. These are short functions (under 20 lines) that exams love to ask for.
True or False: The string "abba" would return 1 from the is_palindrome function.
Fill in the blank: In postfix evaluation, when you encounter an operator, you pop ________ operands from the stack.
True or False: The string "([)]" has balanced parentheses.
Fill in the blank: In the precedence table, * has precedence ________ and + has precedence ________.
True or False: After evaluating a valid postfix expression, the stack should contain exactly one value.
Answers: 1. True. 2. Two. 3. False (the nesting is interleaved, so the types do not match). 4. 2, 1. 5. True.
Q: Trace the stack state for is_balanced on the input "({[]})". Is it balanced?
A: Push (, push {, push [. Hit ], pop [ (match). Hit }, pop { (match). Hit ), pop ( (match). Stack is empty at end. Yes, it is balanced.
Q: Evaluate the postfix expression "4 5 + 3 *" step by step.
A: Push 4, push 5. Hit +: pop 5 and 4, compute 4+5=9, push 9. Push 3. Hit : pop 3 and 9, compute 93=27, push 27. Result: 27.
Q: Why does the palindrome check using a stack require O(n) additional space?
A: Every character in the string is pushed onto the stack, so the stack grows to the same length as the input string.
Q: Convert the infix expression "A + B * C" to postfix using the shunting-yard algorithm.
A: Read A, output A. Read +, push +. Read B, output B. Read , precedence of (2) > precedence of + (1), so push . Read C, output C. End of input: pop , output . Pop +, output +. Postfix: A B C +.
Q: What would is_balanced return for the input "(()"? Why?
A: It returns 0 (unbalanced). After processing all characters, the stack still contains one ( that was never matched, so s.top != -1.
Balanced parentheses is a special case of the more general "matching delimiters" problem, which extends to XML/HTML tag validation. Postfix notation connects directly to how stack-based virtual machines execute bytecode (the Java Virtual Machine, for example, is stack-based). Infix-to-postfix conversion is a gateway topic to compiler design and parsing, which you may encounter in later courses such as COP 4020 (Programming Languages) at UCF.
palindrome, palindrome check, stack palindrome, balanced parentheses, bracket matching, delimiter matching, infix to postfix, shunting-yard algorithm, postfix evaluation, reverse Polish notation, RPN, operator precedence, stack applications, queue word reversal, strtok, COP 3502C, Computer Science I, UCF, C string processing, expression parsing