Parsing algebraic expressions is always a pain. If you need to compute, say, 2+4*2, the answer should be the same as (2 + (4 *2)), not ((2 + 4) * 2) — in other words, the right answer is 10, not 12. The classic way to do this is to use two stacks and a table of precedences for the operators. However, [Martin Janiczek] prefers to use Pratt Parsers and wants to show you how they work.
The parser is named after [Vaughn Pratt]. The algorithm works with a table of precedence where operators with higher precedence have higher numbers. It then builds a left and right portion of a string, using recursion. So if you consider 2+4*2, you wind up, on the first pass, with (2+ parse(4*2)). The second parse returns a full expression to produce: (2+(4*2)).
If that was too fast, read the post which has a nice flowchart and an example step-by-step parse of 1+2-3*4+5/6^7-8*9. Towards the bottom, there’s a nice animated flow chart that you can step through, almost like a debugger.
There are a few details left for the end. For example, there is a way to allow right-associative operators (e.g., 2^3^4 is actually ((2^(3^4)). You can also make some easy modifications to get things like unary negation and parenthesis.
Of course, there are other ways to go. You could stick with RPN. Or use the traditional method.
0 Commentaires