Menu
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?
372
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.
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.
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.
148
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
