'Best Data structure to be used for parsing arithmetic expressions
Suppose that we are going to write a computer code for a parser that parses arithmetic expressions, in simple terms, a program that inspects arithmetic expression for validity. For example, given an arithmetic expression (a / ( b + c) ) x d we would like to see if the parenthesis are matching properly. Which data structure would be the best that can be used to match correct parenthesis in the expression.
Solution 1:[1]
The output of most parsers is either a parse tree showing how the string is structured or an abstract syntax tree showing the semantic meaning of the input string. In your case, if you’re looking for something to the effect of “what parenthesis matches this other one,” you’d probably want a parse tree. You could then match the parenthesis with its soul mate by finding which parse tree node has it as a child.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | templatetypedef |