How to solve a String expression?

This is the sort of task that could be implemented in a couple hours using a tool like JavaCC. However, if you're not familiar with parser generators, it's really easy to get overwhelmed, and the basic idea is the same whether you hand-write the parser or use a generator.

Essentially, any expression will turn into a tree, with the nodes being either constants or subexpressions. You could implement the parse tree using a base class like this (uncompiled, untested):

public abstract class Expression

{

Expression _left;

Expression _right;

public Expression( Expression left, Expression right )

{

_left = left;

_right = right;

}

public abstract int evaluate();

}

You subclass Expression to make the various operators in your language: Addition, Subtraction, &c. For example, the evaluate() method of class Addition would look like this (InvalidExpressionException is an exception that you'd have to define):

public int evaluate()

{

if ((_left != null) && (_right != null))

return _left.evaluate() + _right.evaluate();

else

throw new InvalidExpressionException();

}

OK, that's how you implement and evaluate the parse tree. But how do you build it? Well, you know that there are three different types of expressions:

1) A literal value (in your example: 3, 2, 1). This gets trickier if you want to deal with negative numbers, but I'm sure you'll figure that out.

2) A binary operation, such as "3+2".

3) Another expression wrapped in parenthesis, such as "(3+2)"

One easy way to implement a parser is to have decision logic like the following pseudocode:

if (current token is a paren)

call self, starting at following token

else if (current token is a literal)

look at next token

if (operator)

look for next token to be literal

else if (paren)

call self, starting at following token

else

throw exception

return appropriate Expression subclass based on tokens read

else

throw exception

As I look at this, I realize that it's oversimplified and the logic isn't quite there. But it should be a place to start. Once you've implemented a simple parser like this by hand, parser generators will be much easier to understand, and you'll want to use one for anything more complex :-)

kdgregorya at 2007-7-12 14:22:04 >

In Bjarne Stroustrup's C++ book there is a nice chapter on "A Desk Calculator".

http://www.research.att.com/~bs/3rd_long_tbl.html

6 Expressions and Statements

6.1 A Desk Calculator

6.1.1 The Parser

6.1.2 The Input Function

6.1.3 Low-level Input

6.1.4 Error Handling

6.1.5 The Driver

6.1.6 Headers

6.1.7 Command-Line Arguments

6.1.8 A Note on Style

BIJa at 2007-7-12 14:22:04 >