S
S
sudo rm -rf /2019-05-28 10:32:32
Algorithms
sudo rm -rf /, 2019-05-28 10:32:32

Which text calculator algorithm is better?

There are two console calculators. Both take a text string as input and return the result of the calculation.
The first one recursively (or iteratively) builds a tree, the leaves of which are positive real numbers, and the remaining nodes are operations. To build a tree, the priority of operations is inverted - first, operations with the lowest priority are selected without breaking parentheses. After choosing an operation, the expression is divided into two parts according to the sign of the operation - the operands. Operand expressions are treated as separate expressions: their splitting continues independently of each other. When the result of the calculation of two operands-expressions is received, an operation is performed on the received values. The result of the operation is returned.
Algorithm for a single call to the parsing function Calc(String expr):

  1. Search for operations in expr, taking into account the priority and preserving the bracket structure; or converting a string to a number and returning the value.
  2. Splitting expr into two subexpressions according to the found sign of the operation - oper1, oper2
  3. Recursive partitioning: res1 = Calc(oper1); res2 = Calc(oper2);
  4. Calculation of the result of the found operation on res1 and res2 - o_res.
  5. Return o_res.

At the same time, the second calculator works with the expression "as in school", modifying the string: selects an elementary operation (operands - numbers) with the highest priority, calculates its value, replaces the expression with a value, obtaining a simplified expression and repeats the procedure until a valid number is obtained, which can be reduced and return.
Which of these approaches is better? What are the "pitfalls"?
Are there better alternatives?

Answer the question

In order to leave comments, you need to log in

3 answer(s)
D
dsadso, 2019-05-28
@dsadso

Look at reverse polish notation. The simplest that can be.
https://habr.com/ru/post/100869/

S
Sergey Tikhonov, 2019-05-28
@tumbler

Welcome to the world of constructing compilers :)
In short and simply, the main stages of the compiler are as follows:
So, the first option is, at a minimum approximation, a "competent" interpreter, the second option is a string "crutch" that is hard to debug, maintain and expand.
There are other suitable alternatives: use existing libraries for DSL (an example of which is the problem of calculating mathematical expressions), or write your own grammar and use ready-made solutions for lexical and parsing.

T
tsarevfs, 2019-05-28
@tsarevfs

Polish notation is a simple and unpretentious algorithm. Works with expressions containing binary operations and brackets. Probably your choice.
Downward parsing is what you were trying to describe under the first paragraph. It's more versatile. Allows you to parse more complex grammars with unary operations and context dependency (one character can have different meanings depending on the context). This method has more pitfalls. You need to study a lot of theory to understand how to get around some of the complexities, such as left recursion. With some perseverance, you can figure it out.
Ascending parsing . SLR, LALR parsers. actively applied in practice. They are complex, it makes no practical sense to write them yourself. If you use the Bison parser generator, then this is it.
What you described in the second paragraph is divided into the choice of the operation with the highest priority. In complex cases, this will have to parse the expression in one of the ways I described.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question