# Parsing math notations (Easy)

Printable View

• 11-20-2008
chakram
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!
• 11-20-2008
Adak
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.
• 11-20-2008
bbebfe
Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
• 11-20-2008
zacs7
> Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
Overkill in this case :p
• 11-20-2008
bbebfe
Quote:

Originally Posted by zacs7
> Referring to Lex & Yacc, or Flex & Bison. They are both parser and analyzer generation tools.
Overkill in this case :p

Haha, just a little.
• 11-21-2008
P4R4N01D
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 +
• 11-21-2008
laserlight
A little off topic, but I was puzzled by the term "impix notation". Is that really an alternative name for infix notation?
• 11-21-2008
zacs7
> 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 :-)
• 11-21-2008
master5001
Quote:

Originally Posted by Adak
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?
• 11-21-2008
laserlight
Quote:

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-21-2008
slingerland3g
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.
• 11-21-2008
slingerland3g
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.
• 11-21-2008
P4R4N01D
Quote:

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.