• Post Reply Bookmark Topic Watch Topic
  • New Topic

Fun with stacks  RSS feed

 
Joyce Derzaph
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Author
Ranch Hand
Posts: 253
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's my lash at it (not done this before)
 
Jeff Langr
author
Ranch Hand
Posts: 799
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

Unit tests of course available.
[ March 25, 2004: Message edited by: Jeff Langr ]
 
Michael Dunn
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
author
Ranch Hand
Posts: 799
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
do you mean this:

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

would help in this case
 
Tony Morris
Ranch Hand
Posts: 1608
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
<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
Ranch Hand
Posts: 1608
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
sever oon
Ranch Hand
Posts: 268
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

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

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:

to:

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
author
Ranch Hand
Posts: 799
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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-
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!