Stack isn't pushing element correctly-CodePudding

I am trying to push parts of a string into two different stacks and popping them out so I can see if the string is balanced. For example, we have the sample input of ((())), it would push ( into one stack and it would push ) into another stack. Then it would enter a loop that pops all the characters and if both stacks are empty, it would be balanced. But Im getting this out when I run it.

Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
true

Which I am assuming is that it isn't pushing the characters correctly, I do not know why. Here is a the method

  static boolean isBalanced(String expr){
      // base case: length of the expression must be even
        if (expr == null || expr.length() % 2 == 1) {
            return false;
        }
 
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
 
        // traverse the input expression
        for (int i = 0; i< expr.length(); i  ){ 
            // if the current character in the expression is an opening brace,
            // push it into the stack
            if (expr.charAt(i) == '(') {
                stack1.push(expr.charAt(i));
            } 
 
            // if the current character is closing brace
            if (expr.charAt(i) == ')') {
               stack2.push(expr.charAt(i));
        }
      }
      for(int i = 0; i< expr.length(); i  ) {
        stack1.pop();
        stack2.pop();
      }
      return (stack1.isEmpty() && stack2.isEmpty()) ; 
    }

Here is the stack class

public class Stack{
    private Node top;

    public Stack() {
        top = null;
    }

    public boolean isEmpty(){
        return (top ==null);
    }

    public void push(Object newItem){
        top = new Node(newItem,  top);
    }

    public Object pop(){
        if (isEmpty()){
            System.out.println(
             "Trying to pop when stack is empty");
            return null;
        }else{
            Node temp = top;
            top = top.next;
            return temp.info;
        }
    }


    void popAll(){
        top = null;
    }

    public Object peek(){
        if (isEmpty()){
           System.out.println(
            "Trying to peek when stack is empty");
           return null;
        }else{  
           return top.info;
        }
    }
}// End of Stack using a linked list

Here is the node class

public class Node {
    Object info;
    Node next;
    
    Node(Object info, Node next){
        this.info=info;
        this.next=next;
    }    
}

I am not allowed to import anything and I am only allowed to changed the method, thank you

CodePudding user response：

If I understood the problem correctly, then your mistake is in your second for loop.

  for(int i = 0; i< expr.length(); i  ) {
    stack1.pop();
    stack2.pop();
  }

You are going to pop from each stack expr.length() elements so both stacks are going to be empty at one point.

One possible solution would be to use a while loop whose loop condition is that neither of the 2 stacks are empty.

The moment that one stack is empty you stop the loop, and then your return statement will work just fine because in the moment that one stack is empty, if the other one isn’t also empty the expression isn’t balanced and if they are both empty they are balanced (according to what I understood from your definition of the problem)

CodePudding user response：

The 2nd for-loop:

      ...
      for(int i = 0; i< expr.length(); i  ) {
        stack1.pop();
        stack2.pop();
      }
      ...

runs "too often". In a balanced scenario, both stacks hold expr.length() / 2-may elements, i.e. they are empty() after expr.length() / 2 pop()s, but we pop() expr.length()-times.

The issue can be easily fixed by replacing the 2nd for-loop with a while-loop. I leave the exact condition as an exercise for the reader to figure out.