expression = 0 Solving the equation
Newton's method is the core method of solving. Its Wikipedia's definition is: Newton's method is a method of approximating equations in real and complex fields. The method uses the first few terms of the Taylor series of the function f (x) to find the root of the equation f (x) = 0. In short, Newton's method is to iterate over x until x converges to a small range
Therefore, for any unary function, we can try to use Newton's method to find its approximate solution. When the error is less than 10 ^ -9, or when the number of iteration steps exceeds 10 ^ 5, the iteration ends.
When constructing the solver, there are several key issues that need to be solved: parsing the input expression, expressing the function, deriving the function equation, and substituting and evaluating the function. Among them, the first priority is: how do we store (express) functions?
Why choose this binary expression tree? Mainly because it is a tree structure, which is convenient for recursive processing of nodes, and we later use the recursive idea to derive the function, including the idea of substitution and evaluation.
Preprocessing expressions: First, we need to preprocess the input expression string. Because there are some simple or redundant writing in mathematics that need to be standardized here. After the natural input string is preprocessed, it should be an infix expression string, which is an expression form that humans can naturally understand. But in order to store the expression as a binary expression tree, we also need to convert the infix expression into a postfix expression
Scheduling field algorithm: The degree field algorithm is basically similar to the way we use stack to calculate expressions in stack recursion Hanoi. It uses a queue to express the output suffix expression, and uses the stack to store operators and functions
Build a binary expression tree: Suppose the input expression is: (a + b) * (c * (d + e)). After the scheduling field algorithm, we get the suffix expression of a b + c d e + * *. At this time, we can use the characteristics of suffix expressions to quickly build a binary expression tree.
Evaluation: The algorithm for substituting and evaluating binary expression trees should be easy to think of. Using the recursive nature of the binary tree, the root is an operator or function, and the left subtree and the right subtree are recursively defined. We just need to recursively calculate the values of the left and right subtrees, and then perform the operator operation.
Constructing the Derivative Function Tree: We are left with only the steps to solve the derivative function. This step is also a relatively complicated operation, because the rules of the derivative function are really many. First, the expression derivation function should be represented by a binary expression tree, because it can be directly evaluated and substituted, and the binary expression tree has recursive properties; second, because the root node of the binary expression tree is always The characteristics of the function, the left and right subtrees are also expressions, and we can use the recursive idea to solve the derivative function