Applications of Stacks: Parenthesis Checker, Infix to Postfix, and Evaluation
Explore three important applications of stacks: balanced parenthesis checking, Infix to Postfix conversion, and Postfix expression evaluation, with step-by-step examples and C programs.
In the previous article, we learned how a Stack works and how it follows the LIFO (Last In, First Out) principle.
Now let’s explore three important applications of stacks:
- Checking whether parentheses are balanced.
- Converting an Infix expression into Postfix notation.
- Evaluating a Postfix expression.
1. Checking Balanced Parentheses
Consider a mathematical expression:
( A + B ) * ( C - D )
The parentheses are correctly matched. Every opening parenthesis has a corresponding closing parenthesis.
Now consider:
( A + B ) * ( C - D
Here, one closing parenthesis is missing.
How can a program identify such mistakes?
Using a Stack:
- Whenever an opening bracket
(,{, or[appears, push it onto the stack. - Whenever a closing bracket
),}, or]appears, check the top of the stack. - If the top contains its matching opening bracket, pop it.
- If no matching opening bracket exists, the expression is not balanced.
- At the end, the expression is balanced only if the stack is empty.
Example:
Consider:
{ [ ( A + B ) * C ] }
| Symbol | Action | Stack |
|---|---|---|
{ |
Push | { |
[ |
Push | { [ |
( |
Push | { [ ( |
A + B |
Ignore | { [ ( |
) |
Pop ( |
{ [ |
] |
Pop [ |
{ |
} |
Pop { |
Empty |
Since all brackets have matching pairs and the stack is empty, the expression is balanced.
C Implementation:
#include <stdio.h>
int main() {
char exp[] = "{[(A+B)*C]}";
char stack[100];
int top = -1;
int balanced = 1;
for (int i = 0; exp[i] != '\0'; i++) {
char ch = exp[i];
if (ch == '(' || ch == '[' || ch == '{') {
stack[++top] = ch;
}
else if (ch == ')' || ch == ']' || ch == '}') {
if (top == -1) {
balanced = 0;
break;
}
char open = stack[top--];
if ((ch == ')' && open != '(') ||
(ch == ']' && open != '[') ||
(ch == '}' && open != '{')) {
balanced = 0;
break;
}
}
}
if (top != -1)
balanced = 0;
if (balanced)
printf("Balanced parentheses");
else
printf("Unbalanced parentheses");
return 0;
}
Output:
Balanced parentheses
This technique is useful in compilers and programming language tools for detecting unmatched brackets and syntax errors.
2. Infix to Postfix Conversion
Before understanding the conversion, let’s understand two ways of writing mathematical expressions.
Infix Notation
This is the usual way we write mathematical expressions, where the operator appears between the operands.
A + B
Here:
AandBare <abbr title=”Values or variables on which an operation is performed.”>operands</abbr>.+is an operator.
Postfix Notation
In this form, the operator appears after its operands.
A B +
Both expressions represent the same addition.
Let’s look at another example:
| Infix | Postfix |
|---|---|
A + B |
AB+ |
A + B * C |
ABC*+ |
(A + B) * C |
AB+C* |
Why do we need Postfix notation?
In Infix notation, we must consider operator precedence and parentheses to determine which operation should happen first.
In Postfix notation, the order of operations is already represented by the position of the operators. This makes evaluation straightforward using a stack.
How Does Infix to Postfix Conversion Work?
Consider:
A + B * C
We scan the expression from left to right.
The rules are:
- If we encounter an operand, add it directly to the output.
- If we encounter an opening parenthesis
(, push it onto the stack. - If we encounter an operator, compare its <abbr title=”The priority of an operator. For example, multiplication has higher precedence than addition.”>precedence</abbr> with the operator at the top of the stack.
- Pop operators with higher or equal precedence before pushing the new operator.
- When we encounter a closing parenthesis
), pop operators until the matching(is found. Discard both parentheses. - After scanning the expression, pop any remaining operators onto the output.
Example:
Convert:
A + B * C
| Symbol | Action | Output | Stack |
|---|---|---|---|
A |
Add to output | A |
Empty |
+ |
Push | A |
+ |
B |
Add to output | AB |
+ |
* |
Push (higher precedence) | AB |
+ * |
C |
Add to output | ABC |
+ * |
| End | Pop remaining operators | ABC*+ |
Empty |
The final Postfix expression is:
ABC*+
Notice that multiplication is performed before addition, just as it would be in the original Infix expression.
C Implementation
The following program converts an Infix expression into Postfix notation.
It supports single-character operands, the operators +, -, *, /, and parentheses.
#include <stdio.h>
#include <ctype.h>
int precedence(char op) {
if (op == '*' || op == '/')
return 2;
if (op == '+' || op == '-')
return 1;
return 0;
}
int main() {
char infix[] = "A+B*C";
char stack[100], postfix[100];
int top = -1, k = 0;
for (int i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (isspace(ch))
continue;
if (isalnum(ch)) {
postfix[k++] = ch;
}
else if (ch == '(') {
stack[++top] = ch;
}
else if (ch == ')') {
while (top != -1 && stack[top] != '(')
postfix[k++] = stack[top--];
if (top == -1) {
printf("Invalid expression");
return 0;
}
top--;
}
else {
while (top != -1 &&
stack[top] != '(' &&
precedence(stack[top]) >= precedence(ch)) {
postfix[k++] = stack[top--];
}
stack[++top] = ch;
}
}
while (top != -1) {
if (stack[top] == '(') {
printf("Invalid expression");
return 0;
}
postfix[k++] = stack[top--];
}
postfix[k] = '\0';
printf("Postfix: %s", postfix);
return 0;
}
Output:
Postfix: ABC*+
3. Evaluation of Postfix Expression
Now that we know how to convert an Infix expression into Postfix notation, let’s understand how to calculate the result of a Postfix expression.
Consider:
23*54*+9-
We evaluate it using a stack.
Rules:
- Scan the expression from left to right.
- If the symbol is an operand, push it onto the stack.
- If the symbol is an operator, pop the top two operands.
- Perform the operation and push the result back onto the stack.
- Continue until the expression ends.
Example:
Evaluate:
23*54*+9-
| Symbol | Action | Stack |
|---|---|---|
2 |
Push | 2 |
3 |
Push | 2, 3 |
* |
Calculate 2 × 3 | 6 |
5 |
Push | 6, 5 |
4 |
Push | 6, 5, 4 |
* |
Calculate 5 × 4 | 6, 20 |
+ |
Calculate 6 + 20 | 26 |
9 |
Push | 26, 9 |
- |
Calculate 26 – 9 | 17 |
The final result is:
17
Important: When an operator is encountered, the second element popped is the left operand, and the first element popped is the right operand.
For example, for subtraction:
26 - 9 = 17
The order matters because subtraction and division are not commutative.
C Implementation
The following program evaluates a Postfix expression containing single-digit numbers and the operators +, -, *, and /.
#include <stdio.h>
#include <ctype.h>
int main() {
char exp[] = "23*54*+9-";
int stack[100];
int top = -1;
for (int i = 0; exp[i] != '\0'; i++) {
char ch = exp[i];
if (isdigit(ch)) {
stack[++top] = ch - '0';
}
else {
int b = stack[top--];
int a = stack[top--];
int result;
switch (ch) {
case '+': result = a + b; break;
case '-': result = a - b; break;
case '*': result = a * b; break;
case '/': result = a / b; break;
}
stack[++top] = result;
}
}
printf("Result: %d", stack[top]);
return 0;
}
Output:
Result: 17
This example assumes a valid Postfix expression, with no division by zero.
4. Summary of Stack Applications
| Application | How Stack Is Used |
|---|---|
| Parenthesis Checking | Matches opening and closing brackets |
| Infix to Postfix | Temporarily stores operators |
| Postfix Evaluation | Stores operands and intermediate results |
All three applications use the same basic Stack operations: Push and Pop.
The way we use the stack changes depending on the problem, but the LIFO principle remains the same.
Stacks are useful beyond simply storing and removing elements. They help solve practical problems such as checking balanced parentheses, converting mathematical expressions, and evaluating calculations.
Understanding these applications also helps us see how stacks are used internally by compilers and other computer programs.
In the next article, we’ll explore another important linear data structure: Queue, which follows the FIFO (First In, First Out) principle.
Further reading: NCERT – Stack and Expression Conversion · University of Anbar – Stack Applications
Originally published at farhanpaal.com — https://farhanpaal.com/articles/applications-of-stacks-parenthesis-checker-infix-to-postfix-and-evaluation/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com