How to parse a formula to build up a tree in C#? [closed]

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions seeking recommendation开发者_Go百科s for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed 4 years ago.

Improve this question

If I have a formula:

A = 2+3*5-6/3+2

How could I build up the formula as a tree with nodes, then I can easily calculate the result based on the tree from bottom-up, left to right.

Would someone please provide a sample of the required parser or some references?

---

There are many possible strategies to parsing.

If you want to write the parsing code yourself, then a good strategy is a Recursive descent parser. This is not hard to do, as I wrote one of my own for the C# language.

If you want to use a parser-generator tool, you could use the traditional GNU flex/bison combination, or google for “C# parser generator” to find a C# one so you don’t have to write in C. This would generate an LALR parser.

---

If it's just arithmetic, you can leverage javascript within C# to "eval" the string. If you want to build a proper parser, you'll need to create a grammar, generate a parser from that grammar, and then build an interpreter to process the output of the parser. The GOLD Parsing System is very helpful for that task and has .NET engines, including C#. Other options include the ANTLR Parser Generator and LEX and YACC.

If you really want to roll your own, there are a lot of resources out there. The GOLD Parsing System pages actually have a lot of information about it already:

• Left-to-Right Derivation Parsing
• Deterministic Finite Automata

Etc.

---

If it is simple mathematical expressions then one way is to convert it into reverse polish notation. In this notation it is quite easy to compute the expression because the representation "linearizes" the tree(into a stack). Then the real task parsing and converting in RPN notation(which is very easy actually).

[http://en.wikipedia.org/wiki/Reverse_Polish_notation#Example]

The very old calculators used to use RPN because it was much easier to compute.