Make a tool:convert algebraic expression to functional expression(2)

Posted on In

I got the data structure of stack and binary tree in last article,and finally I got a stack what can describe algebraic expression clearly.Now I can create a expression tree with this stack.

Create the expression tree

This expression tree is a binary tree because each function has 2 arguments commonly.So there are 3 things to describe an algebraic:operator,1st operand(orginal) and 2nd operand.I set binary tree node's left child is the 1st operand,right child is the 2nd operand and its value is the operator.

For example,1+2 is writen 

1
2
3
  +
 / \
1   2

Before create the expression tree,I have to deal with the stack I got before.Because that stack is a reverse array to describe the algebraic expression.

Reverse stack

1
2
stack = Stack()
while origin.length() is not 0: stack.push(origin.pop())

Um..that's all.

And create an empty stack to store the operands temporarily while pop this stack.

Create expression tree and assign elements

1
2
3
4
5
6
7
8
9
while stack.length() is not 0:
    if stack.getTop() in operators:
        node = BiTree(stack.pop())
        node.right = temp.pop()
        node.left = temp.pop()
    else:
        node = BiTree(stack.pop())
    temp.push(node)
return temp.pop()

By this way,I get the correct expression tree.

For example,I input "A+b-x*(12.13+51y)1.4121" before,now I get a binary tree: 

1
2
3
4
5
6
7
8
9
10
11
  +
 / \
A   -
   / \
  b   *
     / \
    +   ^
       / \
      +  1.4121
     / \
   51   y

Traverse the binary tree and create functional expression

This is an iterative process.I convert each child node into a functional expression,such as

1
2
3
  +
 / \
1   2

will change to add(1,2)

And put this functional expression as its parent node's child,and loop again and again,until only one node left. 

1
2
3
4
5
6
operators_name = {'+':'add','-':'mius','*':'muilt','/':'divide','^':'power'}
#create_function_expression
def cfe(Tree):
    if Tree.value in operators_name:
        Tree.value = operators_name[Tree.value] +'('+ cfe(Tree.left) +','+ cfe(Tree.right) +')'
    return Tree.value

Test it,input "A+b-x*(12.13+51y)1.4121" and this script ouput add(A,mius(b,muilt(x,power(add(12.13,power(51,y)),1.4121))))

All script have been uploaded to Github:

https://github.com/lsvih/algebraic-expression-to-function