# Thread: Parsing math notations (Easy)

1. ## Parsing math notations (Easy)

Hi.

Im trying to write a program that can read Strings such as:

1+2*3+4
36-89*3

And return the answer using the correct orders of operation.

Im pretty sure I need to implement some sort of parse tree, but I cant remember how to do that.

Is there a function in the standard library that can do this for me? Or any example source code for one?

thanks!

2. Read Wikipedia and search this forum, for Reverse Polish Notation.

You use 2 stacks, and push and pop numbers and operators on and off. Pretty slick stuff.

3. Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.

4. > Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
Overkill in this case

5. Originally Posted by zacs7
> Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
Overkill in this case
Haha, just a little.

6. Ritchie & Kernighan explain how to evaluate an equation in reverse polish notation, but if you want to read in impix notation (like example above) you will need to use a shunting yard algotithm which I am in the process of writing, need help though. It is easier to work only in reverse polish, e.g. your first example (1+2*3+4) would become something like: 2 3 * 1 + 4 +

7. A little off topic, but I was puzzled by the term "impix notation". Is that really an alternative name for infix notation?

8. > Is that really an alternative name for infix notation?
No. Well no-one I've spoken to has heard of it. Including a maths professor and a CS professor.

My guess is a "communication" error on their side :-)

Read Wikipedia and search this forum, for Reverse Polish Notation.

You use 2 stacks, and push and pop numbers and operators on and off. Pretty slick stuff.
Did he ask for reverse polish notation?

10. Originally Posted by master5001
Did he ask for reverse polish notation?
I am sure that you are aware that converting expressions from infix notation into reverse polish notation as an intermediate step is one way to evaluate expressions in infix notation.

11. Getting into mathmatical analysis can get tricky when dealing with postfix and prefix(Lukasiewicz) methods of the expressions as order of the values is very important, take for instance subtraction and division.

1+2*3+4 ==> 1 2 3 * + 4 + postfix parenthesis are not necesary
36-89*3 ==> 36 89 3 * - postfix

So if you can just rearange the input accordingly then performing the postfix or prefix methods via a function call would be much easier.

12. Forgot to mention that such work makes use of stack behaviour and complicated mathematics are solved this way. "Algorithms in C" addresses this very thing which I happen to be studying atm.

13. Originally Posted by laserlight
A little off topic, but I was puzzled by the term "impix notation". Is that really an alternative name for infix notation?
Sorry, typo. Turns out that went w/ thinking that ASCII was ANCII. Mabye when I first saw the word, I read it too quickly.