Question for you CS guys

[Qubit]

I'm working on this program in C++ where I'd like to get an equation from a user, then parse the equation and do something with the components.

The problem is, I have absolutely no clue of doing this. My question is: how do you tackle such a parsing problem "by the book"?(in other cases I just do strcmp until I know what I want to know, but with maths that's more or less impossible)

A friend of mine suggested to put the formula in a binary tree (for easy evaluation). Any ideas how I should do that?

And when I have that binary tree, won't it be awfully slow to run down that tree every time you need to do a calculation???

Help would be very much appreciated. I'm doing allright on the coding, but this theoretical stuff is really not something I'm good at... (I even had to look in a book for a decent binary tree implementation.)

[AdaHacker]

A binary tree would work. You might go about it by parsing the string with a recursive function. Here's a general idea of how the parsing function would work:

1) Find the lowest precedence operator, i.e. the one you would evaluate last if you were doing it by hand.
2) Assign that operator to a node of the tree.
3) Now parse each operand and assign the result to a child node.

The children may be expressions or atomic values. If they're expressions, you parse them with the same function and assign the resulting node. Actually, you'll want to assign a node no matter what. If the operand is atomic, youll just assign the value to the node and make the children null. When you've parsed everything, you can just traverse the tree, evaluating the nodes as you go. Evaluating a node would also require a recursive function. Straight evaluation for atomic values, recurse for expressions - you get the idea.

If recursion isn't your thing, I vaguely remember doing something like this with a pair of stacks. It didn't use any special operations, i.e. just +, -, /, *, but it worked.

[ 23 January 2002: Message edited by: AdaHacker ]

[Dru Lee Parsec]

You need a parser. I still don't have the new version of Bjrane Stroustrup's book but I know the old gray version of "The C++ Language" used a recursive decent parser as a topic for many of the examples in that book.

It's a cool project. It's also one that's generally the topic of an entire college course in a C.S. degree. Compiler Design was one of my favorite classes.

Believe me, it's not a trivial project.

You may also want to do some research on standard *nix tools called Lex and Bison. They are used to build compilers and parsers.

Have fun.

[sans-hubris]

Why not just convert it to postfix?

[jemfinch]

Originally posted by sans-hubris:
Why not just convert it to postfix?

Converting to postfix requires the equivalent of parsing and evaluating the
equation anyway.

If your grammar is simple enough, you can parse with two simple stacks. For
example, imagine that your grammar requires full parenthesization:

(1+((2*3)/(4-5)))

That is, each subexpression has to be wrapped in parentheses. Such a grammar is
fairly easy to parse. Here's some pythonic pseudocode:


operators = Stack()
operands = Stack()
buffer = ""
c = read_character()
if c = "(":
buffer = ""
elif c in "0123456789":
buffer = buffer + c
elif c in "+-/*":
operands.push(int(buffer))
operators.push(c)
buffer = ""
elif c = ")":
rhs = operands.pop()
lhs = operands.pop()
operator = operators.pop()
if c = "+":
operands.push(lhs + rhs)
elif c = "-":
operands.push(lhs - rhs)
elif c = "*":
operands.push(lhs * rhs)
elif c = "/":
operands.push(lhs / rhs)


For a more complicated grammar (say, without the fully parenthesized
requirement) you'd need to insert some code to check the operator already on the
top of the stack for precedence comparison. For even more complicated grammars
(say, you wanted to support exponentiation, which is right-associative) you'd
have to do even more work. That's why there are numerous automatic parser
generators for this sort of thing.

Jeremy

[sans-hubris]

Originally posted by jemfinch:
<STRONG>Converting to postfix requires the equivalent of parsing and evaluating the
equation anyway.</STRONG>
Yes, but as you had just shown, it would probably be faster to write your own parser rather than going out and trying to use something like Bison or Lex. Something like this is a relatively trivial task.

[Qubit]

Do flex and bison also work for maths? I thought that they were indeed more used for compiler building, or doesn't that matter?

Anyway, my thought was to let the user define his/her own functions/operators/whatever, so I think the stack method looks a bit disadvantageous.

I won't have much time in the next days, but I'll have a go on the implementation during the weekend.

Damn. Now I'm really starting to regret that I didn't take any more computer science courses (other than "Introduction to Pascal" :D)