2

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?

halfer
  • 19,824
  • 17
  • 99
  • 186
olidev
  • 20,058
  • 51
  • 133
  • 197
  • can you add a few more specifics? can the formula have parentheses? are addition, subtraction, multiplication and division the only operations? – vlad Jan 14 '11 at 00:09
  • 1
    [This question](http://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence) is very similar although it is not specific to C#. It might help you get started. – Mark Wilkins Jan 14 '11 at 00:10
  • 2
    This sounds like homework to me. Have you tried anything at all? – Alex Mendez Jan 14 '11 at 00:11
  • exact duplicate of [operators as strings]. My solution even provided the tree. (http://stackoverflow.com/questions/174664/operators-as-strings) – Austin Salonen Jan 14 '11 at 00:14
  • Sounds like a homework assignment for a Compilers class. – Babak Naffas Jan 14 '11 at 00:34
  • I am sorry to create another one. As my first question is not completed and I thought nobody is going to answer it further. Therefore, I created another one. No it is not a homework assignment. I am working on a project of adding more features for the current program written in Java. therefore, for some particular parts from java, I have to rewrite in C#. Thanks for your answers! – olidev Jan 18 '11 at 20:32

3 Answers3

3

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.

Timwi
  • 65,159
  • 33
  • 165
  • 230
2

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:

Etc.

Community
  • 1
  • 1
jball
  • 24,791
  • 9
  • 70
  • 92
2

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.

Stretto
  • 486
  • 2
  • 10