- #1

- 986

- 9

*aaaaallllllmost*there. The intent is to take a math function like

Code:

`x^2+x+1*5`

Code:

```
/ + \
/ + \ / \
/ ^ \ x 1 * 5
x 2
```

Code:

`[Exp_0][Op_1][Exp_1][Op_2][Exp_2].........[Op_n][Exp_n]`

Code:

```
Exp_0 = 'x'
Op_1 = '^'
Exp_1 = 2
Op_2 = '+'
Exp_2 = 'x'
Op_3 = '+'
Exp_3 = 1
Op_4 = '*'
Exp_4 = 5
```

is easy to build into a tree because as you grab the expressions from left to right you simply take the previous tree and make it be the left-hand side of a new tree and make the right-hand side of the tree be the current expression. The building of that tree (skipping a few steps) would look likex^2*2+1

Code:

```
/ ^ \
x 2
```

Code:

```
/ * \
/ ^ \ 2
x 2
```

Code:

```
/ + \
/ 1
/ * \
/ ^ \ 2
x 2
```

Code:

```
Get Exp_0
If there's no Op_1, return Exp_0;
Else,
Make a tree T like
/ [Op_1] \
[Exp_0] [Exp_1]
for (i = 2; i <= n; ++i)
{
temp = T;
T = new Tree;
T.leftHandSide = temp;
T.oper = [Op_i];
T.rightHandSide = [Exp_i];
}
```

The algorithm for making a tree when the precedence of the operators is reversed, e.g.

is slightly more complicated, but I know how to write. I can also write an algorithm that combines the 2 algorithms I mentioned.1+2*x^2

The problem is that I can't think of a general algorithm that looks at the precedence of each operator found and then rebuilds the tree accordingly. It seems like it would be extremely complex, and I've gotten close to making it, but maybe I'm going about things completely wrong.

Can someone give me a hint to push me along?