CODEWITHSUNDEEP
java
TMan
TMan

Reputation: 4122

Testing parentheses in a equation using stack java

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.

Upvotes: 3

Views: 5276

Answers (6)

Griff George
Griff George

Reputation: 895

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

Upvotes: 2

Amanpreet
Amanpreet

Reputation: 526

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!!!");
        }

    }

Upvotes: 0

Kal
Kal

Reputation: 24910

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.

Upvotes: 0

Oosterman
Oosterman

Reputation: 384

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

Upvotes: 1

DaveFar
DaveFar

Reputation: 7457

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

Upvotes: 0

erickson
erickson

Reputation: 269747

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.

Upvotes: 0

Related Questions