Check whether an arithmetic expression has balanced parentheses
  • Posted: 3 years ago
  • Edit
  • answers (1)
  • views (2897)

Suppose you are given an arithmetic expression. How will you check whether it has balanced parentheses or not?


Posted Answers

An arithmetic expression with balanced parentheses will have left and right parentheses in order. Since stack is implemented using LIFO (last in - first out), we can compare the last inserted parentheses in the stack with the current one and check whether they are a pair or not. The algorithm works as follows:


  • Convert the arithmetic expression into a character array.
  • PUSH the left parentheses into the stack.
  • For right parentheses check the status of the stack.

    • If the stack is empty, then the right parentheses has no left pair and return false (not balanced).
    • If the stack is not empty, POP the stack and match it with the right parentheses. If they do not match, return false (not balanced).

  • At the end check the status of the stack. If it is empty, return true (balanced), otherwise false (not balanced).


Example - For an arithmetic expression like ` } ([ ... ])', the algorithm will return false since no left pair of the first ` } ' is found.
For an arithmetic expression like `[{ ( ... }]', the algorithm will return false since the `}' does not match with ` ( '.

Time complexity = O(n) where n is the length of the arithmetic expression.

 
public boolean isExpressionBalanced(char[] expression){
/* Create a new stack */
Stack myStack = new Stack();
/* For each character in the array */
for(int i=0;i <expression.length;i++){
/* Check whether the character is left parentheses */
if(expression[i]=='(' || expression[i]=='{' || expression[i]=='[')
/* Push the left parentheses into the stack */
myStack.push("expression[i]");
/* When it is the right parentheses */
if(expression[i]==')' || expression[i]=='}' || expression[i]==']'){
/* If the stack is empty */
if(isEmpty(myStack))
/* No left pair :: hence not balanced */
return false;
/* Match the right parentheses with the last element of the stack :: not matched :: unbalanced*/
else if(!isParenthesesBalanced(myStack.pop(), expression[i]))
return false;
}
}
/* Check the status of the stack :: If empty, balanced parentheses, otherwise not */
if(isEmpty(myStack))
return true;
else
return false;
}

public boolean isParenthesesBalanced(char c1, char c2){
if(c1=='(' && c2==')')
return true;
else if(c1=='{' && c2=='}')
return true;
else if(c1=='[' && c2==']')
return true;
else
return false;
}

You need to Sign In to post your solution.