-->

Balancing of Brackets in Expression(Application of Stack)

Posted by Admin on
Que : Write a program for checking balancing of brackets in expression. For example :
If expression is [{()}] then it should return true.
If expression is [{{())] then it should return false because  in the expression we have two open {{ but only on one closing } bracket.

Algorithm :

 a) Create a Stack.
b) while(end of input is not reached ) .
    1) If character read is not a symbol ,then ignore it.
    2) If character is an opening bracket like [ , ( , { push it into stack.
    3) If it is a closing symbol and if stack is empty then give error otherwise pop he stack.
    4) If the symbol popped is not the corresponding opening symbol, report an error.


Implementation :
//Creating Node for linked list
class Node {
      char data;
      Node next;

      Node(char d) {
            data = d;
            next = null;
      }
}

// Implementing Stack ADT using linked list
class Stack {
      Node root = null;
      Node newnode;
      Node temp;

      /* push function to add the element at the top */
      public void push(char d) {
            newnode = new Node(d);
            if (root == null) {
                  root = newnode;
            } else {
                  newnode.next = root;
                  root = newnode;
            }
      }

      // pop function to retrieve the element from the top
      public char pop() {
            if (root == null) {
                  return 0;
            }

            char num = root.data;
            Node temp = root.next;
            root = temp;
            return num;
      }

      // function to check whether stack is empty
      public boolean isEmpty() {
            if (root == null)
                  return true;
            else
                  return false;
      }

      // function to return the size(number of elements) of satck
      public int size() {
            Node temp = root;
            int count = 0;
            while (temp != null) {
                  count++;
                  temp = temp.next;
            }
            return count;
      }
}

public class BalancingOfBrackets {
      public static void main(String args[]) {
            String str = "2+{3+(3*4)}]";
            int len = str.length() - 1;
            int i = 0;
            Stack st = new Stack();
            int flag = 1;
            while (i <= len) {
                  char ch = str.charAt(i);
                  if (ch == '{' || ch == '[' || ch == '(') {
                        st.push(ch);
                  }
                  if (ch == '}' || ch == ']' || ch == ')') {
                  char temp = st.pop();
                  if ((ch == ')' && temp == '(') || (ch == '}'&&temp == '{')
                                    || (ch == ']' && temp == '[')) {
                        } else {
                              flag = 0;
                              break;
                        }
                        if (i == len && !(st.isEmpty())) {
                              flag = 0;
                        }
                  }
                  i++;
            }
            System.out.println("flag:" + flag);
            if (flag == 1) {
                  System.out.println("Balance");
            } else {
                  System.out.println("Imbalance");
            }
      }
}

 Please comment if you like the above post or if you find any mistake.


No comments:

Post a Comment