Testing parentheses in a equation using stack java

Question

I'm writing a program that will take in an equation and check if all the parentheses line up and it will output if it is good or not.

For Ex: (3+4) is good ((3*8) is NOT Good

I'm not allowed to use java's built in push() pop() methods ext.. I have to make my own which I think I got....I think! The problem I'm having is in the Test() method.

First I'm not sure how to write the while loop like:

while(there are still characters)

Anyway the output I'm getting is: stack is empty -1

Any help is appreciated. I'm one of the slower program learners and I couldn't be trying any harder. Thanks.

Here's what I got:

public class Stacked {

  int top;
  char stack[];
  int maxLen;

  public Stacked(int max) {
    top = -1; 
    maxLen = max; 
    stack = new char[maxLen];
  }

  public void push(char item) {
    top++;
    stack[top] = item;
  }

  public int pop() {
    //x = stack[top];
    //top = top - 1;
    top--;
    return stack[top];
  }

  public boolean isStackEmpty() {
    if(top == -1) {
      System.out.println("Stack is empty" + top);
      return true;
    } else 
      return false;
  }

  public void reset() { 
    top = -1;
  }

  public void showStack() {
    System.out.println(" ");
    System.out.println("Stack Contents...");
    for(int j = top; j > -1; j--){
      System.out.println(stack[j]);
    }
    System.out.println(" ");
  }

  public void showStack0toTop() {
    System.out.println(" ");
    System.out.println("Stack Contents...");
    for(int j=0; j>=top; j++){
      System.out.println(stack[j]); 
    }
    System.out.println(" ");
  }
//}

  public boolean test(String p ){
    boolean balanced = false;
    balanced = false;
    //while (  ) 
    for(char i = '('; i < p.length(); i++ ){
      push('(');
    }
    for (char j = ')'; j < p.length(); j++){
      pop();
    }
    if (isStackEmpty()) {
      balanced = true;
      //return balanced;
    }
    return balanced;
  } 

  public static void main(String[] args) {
    Stacked stacks = new Stacked(100);
    String y = new String("(((1+2)*3)");

    stacks.test(y);
    //System.out.println(stacks.test(y));
  }    
}

---

Now I'm getting somewhere. I need to be pointed in the right direction again. Thanks everyone this helped big time. I still have a lot more to do but this is good for now. Eventually I need to create a two more methods: one "infix to postfix" and the other "evaluating postfix" and at the end I'll need to read in answers from a text file instead of putting my own into the main method. Thanks again much appreciated.

Answer 1

Unless you need to actually evaluate the equation, a stack is too complicated a solution here. You simply need a counter:

int openParentheses = 0;

for (int i = 0; i < p.length(); i++) {
    if (p.charAt(i) == '(') {
        openParentheses++;
    } else if (p.charAt(i) == ')') {
        openParentheses--;
    }

    //check if there are more closed than open
    if (openParentheses < 0) {
        return false;
    }
}

if (openParentheses == 0) {
    return true;
} else {
    return false;
}

If you absolutely must use stacks, use this:

for (int i = 0; i < p.length(); i++) {
    if (p.charAt(i) == '(') {
        push('x'); //doesn't matter what character you push on to the stack
    } else if (p.charAt(i) == ')') {
        pop();
    }

    //check if there are more closed than open
    if (stackIsEmpty()) {
        return false;
    }
}

if (isStackEmpty()) {
    return true;
} else {
    return false;
}

Answer 2

I agree with Griff except that you should include another check if you didn't have more closed parentheses than open. (x*y))( is not a valid entry.

int openParentheses = 0;

for (int i = 0; i < p.length(); i++) {
    if (p.charAt(i) == '(') {
        openParentheses++;
    } else if (p.charAt(i) == ')') {
        openParentheses--;
    }
    if(openParentheses<0)
       return false;
}

if (openParentheses == 0) {
    return true;
} else {
    return false;
}