### 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

1 | class Stack: |

Data structrue of binary tree

1 | class BiTree: |

(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:

1 | Exp = "A+b-x*(12.13+51^y)^1.4121" |

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

there some unexpected elem “” in this list,filter it!

1 | 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.

1 | def clear_brackets(exp): |

Ps:Must import stack class before:

1 | from data import Stack |

test it!

input:

1 | a = clear_brackets(Exp) |

output:

1 | + |

Try to reduce it:

1 | + |

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.