How to parse mathematical expressions involving parentheses

Question

This isn't a school assignment or anything, but I realize it's a mostly academic question. But, what I've been struggling to do is parse 'math' text and come up with an answer.

For Example - I can figure out how to parse '5 + 5' or '3 * 5' - but I fail when I try to correctly chain operations together.

(5 + 5) * 3

It's mostly just bugging me that I can't figure it out. If anyone can point me in a direction, I'd really appreciate it.

EDIT Thanks for all of the quick responses. I'm sorry I didn't do a better job of explaining.

First - I'm not using regular expressions. I also know there are already libraries available that will take, as a string, a mathematical expression and return the correct value. So, I'm mostly looking at this because, sadly, I don't "get it".

Second - What I've tried doing (is probably misguided) but I was counting '(' and ')' and evaluating the deepest items first. In simple examples, this worked; but my code is not pretty and more complicated stuff crashes. When I 'calculated' the lowest level, I was modifying the string.

So... (5 + 5) * 3

Would turn into 10 * 3

Which would then evaluate to 30

But it just felt 'wrong'.

I hope that helps clarify things. I'll certainly check out the links provided.

Answer 1

Ages ago when working on a simple graphing app, I used this algorithm (which is reasonably easy to understand and works great for simple math expressions like these) to first turn the expression into RPN and then calculated the result. RPN was nice and fast to execute for different variable values.

Of course, language parsing is a very wide topic and there are many other ways of going about it (and pre-made tools for it too)

Answer 2

@Rising Star [I hoped to add this as a comment, but the formatting failed]

It may seem counterintuitive, but a binary tree is both simpler and more flexible. A node, in this case, would be either a constant (number) or an operator. A binary tree makes life somewhat easier when you decide to extend the language with elements like control flow, and functions.

Example:

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

                  '/'
                /     \
              +        2
           /     \
         *         *
       /   \     /   \
      -     5   6     -7
    /   \
   +     1
 /   \
3     4

In the case above the scanner has been programmed to read '-' followed by a series of digits as a single number, so "-7" gets returned as the value component of the "number" token. '-' followed by whitespace is retured as a "minus" token. This makes the parser somewhat easier to write. It fails on the case where you want "-(x * y)", but you can easily change the expression to "0 - exp"