🚀 Programming Example
Parenthesis Matching Using Stack in Java
Learn this program step-by-step with algorithm, source code, output and detailed explanation.
Follow these steps to match parentheses:
( is encountered, push its position into the stack.) is encountered, pop an element from the stack.
import java.util.Stack;
public class ParenthesisMatch {
public static void printMatchedPairs(String expr) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < expr.length(); i++) {
char ch = expr.charAt(i);
if (ch == '(') {
stack.push(i);
}
else if (ch == ')') {
if (!stack.isEmpty()) {
int j = stack.pop();
System.out.println(
") at index " + i +
" matched with ( at index " + j
);
}
else {
System.out.println(
") at index " + i +
" is UNMATCHED!"
);
}
}
}
while (!stack.isEmpty()) {
System.out.println(
"( at index " +
stack.pop() +
" is UNMATCHED!"
);
}
}
public static void main(String[] args) {
String expr1 = "(x+(y-z)*w)";
String expr2 = "((a+b/(c-d))";
System.out.println("Expression: " + expr1);
printMatchedPairs(expr1);
System.out.println("\nExpression: " + expr2);
printMatchedPairs(expr2);
}
}
The Parenthesis Matching Problem is used to check whether every opening parenthesis
( has a corresponding closing parenthesis ) in an expression.
A Stack is the most suitable data structure for solving this problem because it follows the
LIFO (Last In First Out) principle.
(x+(y-z)*w)
0 1 2 3 4 5 6 7 8 9 10 ( x + ( y - z ) * w )
At index 0, the character is (.
Push index 0 into the stack.
Stack = [0]
At index 3, another opening parenthesis is found. Push index 3 into the stack.
Stack = [0, 3]
At index 7, a closing parenthesis is found. Pop the top element from the stack.
) at index 7 matched with ( at index 3
Stack = [0]
At index 10, another closing parenthesis is found. Pop the top element from the stack.
) at index 10 matched with ( at index 0
Stack = []
) at index 7 matched with ( at index 3 ) at index 10 matched with ( at index 0
((a+b/(c-d))
0 1 2 3 4 5 6 7 8 9 10 11 ( ( a + b / ( c - d ) )
) at index 10 matched with ( at index 6 ) at index 11 matched with ( at index 1
After processing all characters, one opening parenthesis remains in the stack.
Stack = [0]
Therefore, the output will be:
( at index 0 is UNMATCHED!
A stack follows the LIFO (Last In First Out) principle. The most recently inserted opening parenthesis should be matched first when a closing parenthesis is encountered.
Push first ( Push second ( Stack: [0, 3] When ')' appears: Pop 3 first Pop 0 later
This behavior perfectly matches the rule that the most recently opened parenthesis must be closed first. Therefore, a stack is the ideal data structure for solving the parenthesis matching problem.
| Operation | Complexity |
|---|---|
| Traversing the Expression | O(n) |
| Push Operation | O(1) |
| Pop Operation | O(1) |
| Overall Complexity | O(n) |
Here, n represents the length of the expression.
The Parenthesis Matching Problem is a classic application of the Stack data structure. By using push and pop operations, we can efficiently determine whether an expression contains balanced parentheses. This is one of the most commonly asked stack-based programming questions in interviews and examinations because it demonstrates a practical real-world use of stacks.
First understand the algorithm carefully. Then study the program line-by-line and compare it with the output. Finally, review the explanation section to strengthen your logic and programming understanding.
Rewrite the program without looking at the code. Modify values, conditions or logic and run it again. This helps improve confidence and strengthens coding skills much faster.