• Posted: 6 years ago
• Updated: 6 years ago
• 0 0
• Edit

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).
  

 
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;
 }