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.

Do you have to use a stack, or are you allowed to use recursion? — erickson, Sep 14 '11 at 17:25
the loop over the characters should be done with a for loop -- for (int i = 0; i < p.length(); p++) { char c = p.charAt(i); } -- You could transform that into a while if you like but the for is more readable. — Rontologist, Sep 14 '11 at 17:29
Also see http://stackoverflow.com/questions/196830/what-is-the-easiest-best-most-correct-way-to-iterate-through-the-characters-of-a for iterating over characters in a strng — Rontologist, Sep 14 '11 at 17:29
Loop over characters into given string. Instead of doing "while there are characters left in the string" you can do "for each character in the string" — Rontologist, Sep 14 '11 at 18:04

Griff George · Accepted Answer · 2011-09-14T17:52:59.540

2

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

edited Sep 14 '11 at 17:52

answered Sep 14 '11 at 17:35

Griff George

895
7
17

1

Rather than an if-else statement, it's cleaner just to return the boolean result of the conditional expression: `return openParentheses == 0;` or `return isStackEmpty();` – erickson Sep 14 '11 at 17:42
@erickson I agree completely, however when I was a complete beginner, I found if-else statements easier to follow. – Griff George Sep 14 '11 at 17:45
Heres the problem now. I have it working but If put good equation in like: (3+4) it gives me an arrayoutofboundsexception error – TMan Sep 14 '11 at 18:09
@Tony Lagarrigue, in the `for` loop, did you use `i <= p.length()` or `i < p.length()`? It should just be `<`, because the value of `p.length()` is not actually a valid index. i.e. If there are `n` chars in your string, they are indexed `0` to `n-1`. – Griff George Sep 14 '11 at 18:17

score 1 · Answer 2 · answered Sep 14 '11 at 17:41

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

Kal · Answer 3 · 2011-09-14T17:49:38.737

I think you just need this --

for ( int i = 0 ; i < p.length(); i++ ) {

    char c = p.charAt(i);
    if ( c == '(' ) 
        push('(');
    else if ( c == ')' ) {
        if ( isStackEmpty() ) {
          // Return error here because of unbalanced close paranthesis
        }
        pop();
    }
    else {
      // do nothing
    }
}

You CAN use a stack if you must, but considering how simplistic this is, you just need a counter that you increment and decrement and check for 0 at the end. If you do use a counter, you should check after every decrement if the value is less than 0. If so, throw an error.

Edited based on Ryan/Dave Ball's comments.

See Ryan's comment for Griff's answer: only checking for 0 at the end is not sufficient. — DaveFar, Sep 14 '11 at 17:43

score 0 · Answer 4 · answered Sep 14 '11 at 17:40

You may be required to use a stack, but this could be done with a simple counter. This will show you a how to iterate over the characters of a String:

boolean test(String p) {
  int balance = 0;
  for (int idx = 0; idx < p.length(); ++idx) {
    char ch = p.charAt(idx);
    if (ch == '(')
      ++balance;
    else if (ch == ')')
      --balance;
    if (balance < 0)
      return false;
  }
  return balance == 0;
}

Of course, you could replace the increment and decrement with pushes and pops, respectively, on a stack.

score 0 · Answer 5 · answered Sep 14 '11 at 17:40

0

For parsing you can use a for loop over the index and address the character of the string at the certain index.

But you actually do not need a stack, an integer variable openBraces is sufficient:

initialize with 0
for '(' you increment the variable one
for ')' you decrement the variable one
if openBraces is <0, you immediately give an error
if at the end openBraces is not equal to 0, you give an error.

Since you should do your homework yourself, I did not post source code, only explanations ;)

answered Sep 14 '11 at 17:40

DaveFar

7,078
4
50
90

I respect what you said about not doing my homework. I appreciate the help you did give me. Here's the thing, I'm required to use stacks and there's a big difference between writing someone's homework, and writing a small piece of code for someone to "help" someone with their homework. Even giving an example of how to write a piece of code is better than nothing. :) – TMan Sep 14 '11 at 20:57
My comment was meant to be somewhat humorous, so don't take it too serious. I did not want to post code because I've seen people getting downvotes here for doing someone else's homework.... I think I was the first one getting the algorithm right, though ;) – DaveFar Sep 14 '11 at 21:46
I gotcha, like I said I respect that its no problem. I didn't mean to sound like a dick or anything. – TMan Sep 15 '11 at 17:41

score 0 · Answer 6 · answered Sep 14 '11 at 17:50

It could be done like this:

String equation = "(2+3))";
        Integer counter = 0;
        //while(equation)
        for(int i=0; i<equation.length();i++)
        {
            if(equation.charAt(i)=='(')
            {
                counter++;
            }
            else
            if(equation.charAt(i)==')')
            {
                counter--;
            }
        }
        if(counter == 0)
        {
            System.out.println("Is good!!!");
        }
        else
        {
            System.out.println("Not good!!!");
        }

    }

Testing parentheses in a equation using stack java

6 Answers6