Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

parsing math expression in c++

Tags:

c++

parsing

tree

I have a question about Parsing Trees:

I have a string (math expresion estring), for example: (a+b)*c-(d-e)*f/g. I have to parse that expression in a Tree:

class Exp{}; class Term: public Exp{     int n_; }  class Node: Public Exp{     Exp* loperator_;     Exp* roperator_;     char operation; // +, -, *, / } 

What algorithm can I use to build a tree which represents the expresion string above?

like image 372
Emiliano Gustavo Nunez Avatar asked Jul 28 '12 17:07

Emiliano Gustavo Nunez


People also ask

What is parsing in math?

Parser: Reads the tokens outputted from the lexer and parses them into a structure such as RPN or AST. It reshapes the tokens into a structure according to rules such as operator preceedance.

What does parsing an expression mean?

Parsing is the process of analysing a string of symbols, expressed in natural or computer languages that will accord formal grammar. Expression Parsing in Data Structure means the evaluation of arithmetic and logical expressions.


1 Answers

Use the Shunting-yard algorithm. The wikipedia description is quite comprehensive, I hope it will suffice.

You can also try to write a formal grammar, for example a parsing-expression grammar, and use a tool to generate a parser. This site about PEGs lists 3 C/C++ libraries for PEG parsing.

like image 148
Kos Avatar answered Sep 21 '22 18:09

Kos