If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see how to check for balanced parentheses in an expression.
Lets say, you have expression as a*(b+c)-(d*e)
If you notice, above expression have balanced parentheses.
Lets take another expression as (a*(b-c)*(d+e)
If you observe, above expression does not have balanced parentheses.
We will use stack data structure to check for balanced parentheses.
Algorithm:
- Whenever you encounter current character as ( or { or [, push it into the stack.
- Whenever you encounter current character as ) or } or ], retrieve last element from stack and check if current character is in pair with last character retrieved from stack and if it is not in pair then expression is not balanced.
- If we have empty stack in the end, it is balanced parentheses, else it is not balanced parentheses.
Java Program to check for balanced parentheses:
Create a main Class called CheckBalancedParentesisMain.java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package org.arpit.java2blog; import java.util.Stack; public class CheckBalancedParentesisMain { public static void main(String[] args) { String checkBalancedExpr1=checkBalancedParentesis("a*(b+c)-(d*e)"); System.out.println("a*(b+c)-(d*e) : "+checkBalancedExpr1); String checkBalancedExpr2=checkBalancedParentesis("(a*(b-c)*{d+e}"); System.out.println("(a*(b-c)*{d+e} : "+checkBalancedExpr2); } public static String checkBalancedParentesis(String expr) { if (expr.isEmpty()) return "Balanced"; Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < expr.length(); i++) { char current = expr.charAt(i); if (current == '{' || current == '(' || current == '[') { stack.push(current); } if (current == '}' || current == ')' || current == ']') { if (stack.isEmpty()) return "Not Balanced"; char last = stack.peek(); if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[') stack.pop(); else return "Not Balanced"; } } return stack.isEmpty()?"Balanced":"Not Balanced"; } } |
|
1 2 3 4 |
a*(b+c)-(d*e) : Balanced (a*(b-c)*{d+e} : Not Balanced |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
