0%

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

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+51^y)^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+51^y)^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