Fun with stacks

[Joyce Derzaph]

Ok, this is supposed to be an easy assignment. I think I'm making it more complicated than it has to be.
Using stacks, I have to determine whether an expression is well bracketed or not.
eg. 3*(5+9)/4 well bracketed
(4*[4+7)] not
If I could just use a linked list and match the brackets from each end I could do it but my mind doesn't want to do it from one end.
Any suggestions?
Joyce

[Joyce Derzaph]

I guess it might help if I post what I have so far.
public boolean checkExpression(String expr)
{
int size = expr.length();
SLLStack bracketStack = new SLLStack();
char char2;
for(int x=0; x<size; x++)
{
char char1 = expr.charAt(x);
switch(char1)
{
case '(': case '[': case '{': case ')': case ']': case '}':
{
bracketStack.push(char1);
break;
}
case '/':
{
if(exprStack.peek() == '*' || exprStack.peek() == '/')
{
bracketStack.push(exprStack.pop());
}
}
}
}
char char3 = bracketStack.pop();
if(char3 == '('||char3 == '{'||char3 == '[')
{
return false;
}

[Herb Schildt]

Joyce:
If I understand your problem correctly, then here is a procedure that you can try.
Use a separate stack for each type of bracket. Read the expression, character by character, from left to right. Each time you see an opening bracket, push it on the appropriate stack. Each time you see a closing bracket, pop the corresponding stack. When you reach the end of the expression, if it is properly bracketed, then the stacks will be empty.

[Michael Dunn]

Here's my lash at it (not done this before)

import java.util.Stack;
class WellBracketed
{
  public WellBracketed()
  {
    Stack stack = new Stack();
    String opening = "({[";
    String closing = ")}]";
    String expression = "3*(5+9)/4";
    //String expression = "(4*[4+7)] ";
    int pos;
    String bracket;
    boolean wellBracketed = true;
    for(int x = 0; x < expression.length(); x++)
    {
      bracket = expression.substring(x,x+1);
      if(opening.indexOf(bracket) > -1) stack.push(bracket);
      else if((pos = closing.indexOf(bracket)) > -1)
      {
        if(!((String)stack.peek()).equals(opening.substring(pos,pos+1)))
        {
          wellBracketed = false;
          break;
        }
        else stack.pop();
      }
    }
    System.out.println("The expression being well bracketed is "+wellBracketed);
    System.exit(0);
  }
  public static void main(String[] args){new WellBracketed();}
}

[Jeff Langr]

I think the last code fails on test cases "((a*b) + [c*a)" and "(asda". It's a minor fix, but here's my two cents anyway--pretty much what Schildt suggested, except it uses a single stack:

import java.util.*;
public class Expression {
   private static Map parens;
   static {
      parens = new HashMap();
      parens.put(new Character(')'), new Character('('));
      parens.put(new Character(']'), new Character('['));
      parens.put(new Character('}'), new Character('{'));
   }
   public static boolean isWellFormed(String expression) {
      Stack stack = new Stack();
      for (int i = 0; i < expression.length(); i++) {
         Character ch = new Character(expression.charAt(i));
         if (isLeftParen(ch))
            stack.push(ch);
         else if (isRightParen(ch))
            if (stack.isEmpty() || !stack.pop().equals(getCorrespondingLeftParen(ch)))
               return false;
      }
      return stack.isEmpty();
   }
   private static boolean isLeftParen(Character ch) {
      return parens.values().contains(ch);
   }
   private static boolean isRightParen(Character ch) {
      return parens.keySet().contains(ch);
   }
   private static Character getCorrespondingLeftParen(Character rightParen) {
      return (Character)parens.get(rightParen);
   }
}

Unit tests of course available.
[ March 25, 2004: Message edited by: Jeff Langr ]

[Michael Dunn]

I think the last code fails on test cases.....

Quite correct, thanks.
Seems to be fixed if I add (immediately after the end of the for loop)
if(!stack.isEmpty())wellBracketed = false;
Probably other errors (usually is), but one fix at a time.

[Jeff Langr]

Greetings Michael,
That looks like it'll fix it.
But it's also one reason that, instead of one fix at a time, I build my code up one "correct" increment at a time, by building a suite of unit tests and coding the tests first. I had a similar problem as you, but recognized it as soon as I added an assertion to cover that case.
-Jeff-

[Stefan Wagner]

Joyce:
Some samples as questions, whether they are 'well braced'
'a*(b+)c'
'()'
'a*(b)'
'a*((b+c))'
'a+(-b)'
'a+*/b'
'a(b)'

[Joyce Derzaph]

Thanks for the help everyone. This makes much more sense now.
Any ideas on why I cant' cast the object from peek() to a string even though that's what it was before it was added to the stack?
Probably something simple I can't see because I've been staring at it so long my eyes are square.
Ahh, the joys of debugging.
Joyce

[Stefan Wagner]

do you mean this:

 
if(exprStack.peek() == '*' || exprStack.peek() == '/')

I don't know exprStack.peek(), but it is called twice, if the first call returns '/'.

 
esp = exprStack.peek();
if(esp == '*' || esp == '/')

would help in this case

[Tony Morris]

<hack>
[CODE]
// the java.util.Stack class is broken, but will be used only for this example
import java.util.Stack;
class X
{
public static void main(String[] args) throws BracketsBrokenException
{
if(args.length == 0)
{
System.err.println("Provide an argument to check for bracket consistency");
}
else
{
Stack s = new Stack();
for(int i = 0; i < args[0].length(); i++)
{
Bracket b = Bracket.getBracket(args[0].charAt(i));
if(b == Bracket.OPEN_PARENTHESIS || b == Bracket.OPEN_BRACKET || b == Bracket.OPEN_BRACE)
{
s.push(b);
}
else if(b == Bracket.CLOSE_PARENTHESIS)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_PARENTHESIS);
}
Object o = s.pop();
if(o != Bracket.OPEN_PARENTHESIS)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_PARENTHESIS + " found " + o + " instead");
}
}
else if(b == Bracket.CLOSE_BRACKET)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_BRACKET);
}
Object o = s.pop();
if(o != Bracket.OPEN_BRACKET)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_BRACKET + " found " + o + " instead");
}
}
else if(b == Bracket.CLOSE_BRACE)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_BRACE);
}
Object o = s.pop();
if(o != Bracket.OPEN_BRACE)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_BRACE + " found " + o + " instead");
}
}
}
if(!s.empty())
{
Object o = s.pop();
throw new BracketsBrokenException("No Match found for " + o);
}
}
}
}
class Bracket
{
private char c;
private Bracket(char c)
{
this.c = c;
}
public char getChar()
{
return c;
}
public String toString()
{
return String.valueOf(c);
}
public static Bracket getBracket(char c)
{
if(c == '(')
{
return OPEN_PARENTHESIS;
}
else if(c == ')')
{
return CLOSE_PARENTHESIS;
}
else if(c == '[')
{
return OPEN_BRACKET;
}
else if(c == ']')
{
return CLOSE_BRACKET;
}
else if(c == '{')
{
return OPEN_BRACE;
}
else if(c == '}')
{
return CLOSE_BRACE;
}
return null;
}
public static Bracket OPEN_PARENTHESIS = new Bracket('(');
public static Bracket CLOSE_PARENTHESIS = new Bracket(')');
public static Bracket OPEN_BRACKET = new Bracket('[');
public static Bracket CLOSE_BRACKET = new Bracket(']');
public static Bracket OPEN_BRACE = new Bracket('{');
public static Bracket CLOSE_BRACE = new Bracket('}');
}

class BracketsBrokenException extends Exception
{
public BracketsBrokenException()
{
super();
}
public BracketsBrokenException(String message)
{
super(message);
}
}
[CODE]
</hack>
My excuse: "I was bored"

[Tony Morris]

  
// the java.util.Stack class is broken, but will be used only for this example
import java.util.Stack;
class X
{
public static void main(String[] args) throws BracketsBrokenException
{
if(args.length == 0)
{
System.err.println("Provide an argument to check for bracket consistency");
}
else
{
Stack s = new Stack();
for(int i = 0; i < args[0].length(); i++)
{
Bracket b = Bracket.getBracket(args[0].charAt(i));
if(b == Bracket.OPEN_PARENTHESIS || b == Bracket.OPEN_BRACKET || b == Bracket.OPEN_BRACE)
{
s.push(b);
}
else if(b == Bracket.CLOSE_PARENTHESIS)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_PARENTHESIS);
}
Object o = s.pop();
if(o != Bracket.OPEN_PARENTHESIS)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_PARENTHESIS + " found " + o + " instead");
}
}
else if(b == Bracket.CLOSE_BRACKET)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_BRACKET);
}
Object o = s.pop();
if(o != Bracket.OPEN_BRACKET)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_BRACKET + " found " + o + " instead");
}
}
else if(b == Bracket.CLOSE_BRACE)
{
if(s.empty())
{
throw new BracketsBrokenException("No mtach for " + Bracket.CLOSE_BRACE);
}
Object o = s.pop();
if(o != Bracket.OPEN_BRACE)
{
throw new BracketsBrokenException("No matching " + Bracket.OPEN_BRACE + " found " + o + " instead");
}
}
}
if(!s.empty())
{
Object o = s.pop();
throw new BracketsBrokenException("No Match found for " + o);
}
}
}
}
class Bracket
{
private char c;
private Bracket(char c)
{
this.c = c;
}
public char getChar()
{
return c;
}
public String toString()
{
return String.valueOf(c);
}
public static Bracket getBracket(char c)
{
if(c == '(')
{
return OPEN_PARENTHESIS;
}
else if(c == ')')
{
return CLOSE_PARENTHESIS;
}
else if(c == '[')
{
return OPEN_BRACKET;
}
else if(c == ']')
{
return CLOSE_BRACKET;
}
else if(c == '{')
{
return OPEN_BRACE;
}
else if(c == '}')
{
return CLOSE_BRACE;
}
return null;
}
public static Bracket OPEN_PARENTHESIS = new Bracket('(');
public static Bracket CLOSE_PARENTHESIS = new Bracket(')');
public static Bracket OPEN_BRACKET = new Bracket('[');
public static Bracket CLOSE_BRACKET = new Bracket(']');
public static Bracket OPEN_BRACE = new Bracket('{');
public static Bracket CLOSE_BRACE = new Bracket('}');
}

class BracketsBrokenException extends Exception
{
public BracketsBrokenException()
{
super();
}
public BracketsBrokenException(String message)
{
super(message);
}
}

[sever oon]

You guys are writing an AWFUL lot of code to do this. I'd write my own Stack to begin with, because the java.util.Stack is based on the pre-Collections Vector and that's no good:

public class Stack
{
  private List list = new LinkedList();
  public boolean push( String s ) { return list.add(s); }
  public String peek()            { return (String) list.get(list.size() - 1); }
  public String pop()             { return (String) list.remove(list.size() - 1); }
  public int size()               { return list.size(); }
  public boolean isEmpty()        { return list.isEmpty(); }
}

There.
Now use a StringTokenizer to look for brackets, braces, etc.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
public class ExpressionAnalyzer
{
  public static void main( String[] args ) {
    final ExpressionAnalyzer ea = new ExpressionAnalyzer();
    if( args.length != 1 ) {
      System.out.println( "Usage: " + ea.getClass().getName() + " 'expr'" );
      System.exit( 1 );
    }
    final String e = args[0];
    System.out.print( "'" + e + "' is " );
    if( !ea.isWellFormed(e) ) {
      System.out.print( "NOT " );
    }
    System.out.println( "well formed" );
  }
  private final Stack stack = new Stack();
  private final List open = Arrays.asList( new String[] { "(", "[", "{" } );
  private final List close = Arrays.asList( new String[] { ")", "]", "}" } );
  public boolean isWellFormed( final String expr ) {
    boolean wellFormed = true;
    final StringTokenizer stok = new StringTokenizer( expr, getTokens(), true );
    while( stok.hasMoreTokens() ) {
      final String tok = stok.nextToken();
      if( isOpen(tok) ) {
        stack.push( tok );
      }
      else if( isClose(tok) ) {
        if( stack.isEmpty()  || !isMatch(stack.pop(), tok) ) {
          wellFormed = false;
          break; // don't iterate while loop anymore
        }
      }
    }
    return wellFormed;
  }
  public String getTokens() {
    final StringBuffer toks = new StringBuffer( open.size() + close.size() );
    for( int i=0; i < open.size(); i++ ) { toks.append( open.get(i) ); }
    for( int i=0; i < close.size(); i++ ) { toks.append( close.get(i) ); }
    return toks.toString();
  }
  public boolean isOpen( String tok ) { return open.contains( tok ); }
  public boolean isClose( String tok ) { return close.contains( tok ); }
  public boolean isMatch( String openToken, String closeToken ) {
    boolean match = false;
    if( isOpen(openToken)  &&  isClose(closeToken) ) {
      match = open.indexOf( openToken ) == close.indexOf( closeToken );
    }
    else {
      match = false;
    }
    return match;
  }
}
class TestStack extends Stack
{
  public boolean push( final String s ) {
    System.out.println( "push: " + s );
    return super.push( s );
  }
  public String pop() {
    final String s = super.pop();
    System.out.println( "pop: " + s );
    return s;
  }
}

I included a TestStack class as well that you can use to see what's being pushed and popped. In the ExpressionAnalyzer class, just change the line:

private final Stack stack = new Stack();

to:

private final Stack stack = new [B]Test[/B]Stack();

Pass in the expression to be analyzed on the command line, like this:
---------------------------------
>java ExpressionAnalyzer ()
'()' is well formed
>java ExpressionAnalyzer (}
'(}' is NOT well formed
---------------------------------
Incidentally, one thing you should note. This class depends upon an opening token being at the same index in List open as the matching closing token. For example, if you look at the open and close Lists in my code above, the open paren and close paren are both at index 0. The open brace and close brace are both at index 2. You can add as many as you want, just make sure the position of the opening token in the open List matches the position of the closing token in the close list.
sev
[ March 28, 2004: Message edited by: sever oon ]

[Jeff Langr]

Greetings Sever,
1. New use of StringTokenizer is discouraged. (Honestly, I just found this out myself, having not used 1.4 much but 1.3/earlier and 1.5 extensively.) Sun recommends use of the regex package instead. In any case, I didn't see the need for either here.
2. For a short problem like this, use of java.util.Stack is fine, even though it uses Vector. Also, instead of constructing a new stack class, why not just use a LinkedList? "addLast" and "removeLast" are suitable idiomatic replacements for push and pop.
3. You chastised the other programmers for writing so much code. Yet my solution (way above) was the most succinct, without being obtuse, at 30 source lines, far less than what you produced (even if you don't count your test code, the custom stack class, and the main driver). (I did write tests for mine but chose not to post them.)
So, I challenge you to see if you can make your solution cleaner!
-Jeff-