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

Introduction

My colleague,Tu is writing a programme for calculation of money in bank.Those algebraic expression are complicated.And he write program with Java.So when he is writing functional expression in Java,he is confusion because there are too much functions and brackets.

To save him in brackets' sea,I plan to make an tool to convert algebraic expression to functional expression.

I will use Python to do that.

First,I consider commonly operators are functions have 2 arguments,so I can construct binary tree to store algebraic expression.

Second,it is likely that many brackets in expression.So I consider using stack to deal those brackets.

Review:

Data structure of stack

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items)==0

    def push(self,item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def getTop(self):
        if not self.is_empty():
            return self.items[len(self.items)-1]

    def length(self):
        return len(self.items)

    def clear(self):
        self.__init__()

Data structrue of binary tree

class BiTree:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def clear(self):
        self.__init__()

    def is_empty(self):
        return self.value is None

    def depth(self,node):
        if node.value is None or node is None:
            return 0
        else:
            l_length = self.depth(node.left)
            r_length = self.depth(node.right)
            if l_length>=r_length:
                return l_length+1
            else:
                return r_length+1

    def value(self):
        return self.value

    def per_order_traverse(self, node):
        if node is None or node.value is None:
            return
        print node.value
        self.per_order_traverse(node.left)
        self.per_order_traverse(node.right)

    def in_order_traverse(self, node):
        if node is None or node.value is None:
            return
        self.in_order_traverse(node.left)
        print node.value
        self.in_order_traverse(node.right)

    def post_order_traverse(self, node):
        if node is None or node.value is None:
            return
        self.post_order_traverse(node.left)
        self.post_order_traverse(node.right)
        print node.value

(It is not good to put those additional function in data structrue.lol)

Covert algebraic expression to binary tree

This binary tree describes the whole computational procedure so it always called expression tree.

To get more information about expression tree,visite CS1112 in The George Washington University：

https://www.seas.gwu.edu/~mtdiab/Courses/CS1112/lectures/module10/module10Supp.html

(1)Break expression

Un,when I got an algebraic expression like "x+(y-31)^1.4+10*N",I will break it into an list at first.

Like this:

Exp = "A+b-x*(12.13+51^y)^1.4121"
operators = {'(':0,')':0,'+':1,'-':1,'*':2,'/':2,'^':3}
for op in operators:
    Exp = Exp.replace(op,'|'+op+'|')
Exp = Exp.split('|')

out print ['A', '+', 'b', '-', 'x', '*', '', '(', '12.13', '+', '51', '^', 'y', ')', '', '^', '1.4121']

there some unexpected elem "" in this list,filter it!

Exp = [item for item in Exp if not item is ""]

Finally I got ['A', '+', 'b', '-', 'x', '*', '(', '12.13', '+', '51', '^', 'y', ')', '^', '1.4121']

Ps:I find that it is difficult to consider the situation when expression has negative item....

TODO:consider the negative item!

(2)Consider those brackets

Brackets will change the step of calculate,so I have to cope them before constructing expression tree.

I set an empty stack,when I meet "(" in expression,I will push this bracket and elems behind it into stack.When i meet ")" in expression,I will pop stack's elems until the next "(" is out from stack.

By this way,I will get an correct order list of calculation whitout bracket.

def clear_brackets(exp):
    temp = Stack()
    result = Stack()
    for elem in exp:
        if elem not in operators:
            result.push(elem)
        else:
            if temp.length() is 0 or elem is '(':
                temp.push(elem)
            else:
                if elem is ')':
                    while temp.getTop() is not '(':
                        result.push(temp.pop())
                    temp.pop()
                elif operators[elem] < operators[temp.getTop()]:
                    while temp.length() is not 0:
                        if temp.getTop() is '(':
                            break
                        result.push(temp.pop())
                    temp.push(elem)
                else:
                    temp.push(elem)
    while temp.length() is not 0:
        result.push(temp.pop())
    return result

Ps:Must import stack class before:

from data import Stack
from data import BiTree

test it!

input:

a = clear_brackets(Exp)
while a.length() is not 0:
    print a.pop()

output:

+
-
*
^
1.4121
+
^
y
51
12.13
x
b
A

Try to reduce it:

+
-
*
^
1.4121
+
^
y
51
12.13
x
b
A
===========
+
-
*
^
1.4121
+
51^y
12.13
x
b
A
==========
+
-
*
^
1.4121
12.13+51^y
x
b
A
==========
+
-
*
(12.13+51^y)^1.4121
x
b
A
==========
+
-
x*(12.13+51^y)^1.4121
b
A
==========
+
b-x*(12.13+51^y)^1.4121
A
==========
A+b-x*(12.13+51^y)^1.4121

Perfect!I got the original expression,it says this function is work normally.

summary

Now,the original expression is converted to a ordered stack.I will convert this stack to expression tree later.