Arithmetic Expression Detection and Replacement in a Tree

[Seeker]

Given an arithmetic expression (containing binary operators and brackets) that is stored in a tree I have to be able to search for a subexpression and replace the entire subtree for that subexpression with its value.

What firstly came to my mind is that I can reduce that expression to (R)PN (=(Reverse) Polish Notation) since any expression can be reduced to that. For example (3/2/5) can be written as (3/1)*(5/2) and then build a tree from it. To calculate the value for a (sub)expression I can operate with a stack and then append it back to the tree.

I would really apreciate if you can suggest different approaches to this in terms of complexity and memory usage.

[ventsyv]

I'm not sure what (3/2/5) means. Is it (3/2)/5 ? Whatever it is, it is not equal to (3/1)*(5/2)
(3/1)*(5/2)=7.5 and (3/2)/5=0.3
Anyways, even if it was equal, that is not Reverse polish notation. (3/2/5) (as in (3/2)/5 ) in RPN will be 32/5/. I have not done RPN in a while and I'm doing this in my head so it might be wrong.

I suggest you you some variation of expression tree. Google it there should be a number of tutorials out there. Since you have the whole expression, you can use the mathematical operators to select which way to go in the tree. You can build you substitute expression in a tree of its own, and than just re-link the parent node of the subtree (subexpression) that you are substituting to the new subexpression.
Just remember to release the memory the old expression is using

Do you need to be using tree BTW ?

[Seeker]

Yes, a tree is mandatory.

If (3/2/5) is (3/(2/5)) (Which is what I actually wanted to say), we can translate it to (3*(5/2)) ( the same with ((3/1)*(5/2)) - with the idea in mind that a proper binary tree should be build) and then build a binary tree from it ( the RPN is (3 1 / 5 2 / *) ).

To obtain the RPN from a binary tree I just have to traverse it in post-order or applying Djkstra's Shunting Yard algorithm on an infix expression (only stack and queue required).

Yes, linking the subtree to its parent is a good idea.

Unfortunately, I still have no idea on how to calculate the value of a subexpression (subtree) without using an auxiliary stack .

If you guys come up with anything else please let me know.

[Alvaro]

Given an arithmetic expression (containing binary operators and brackets) that is stored in a tree I have to be able to search for a subexpression and replace the entire subtree for that subexpression with its value.

Unfortunately, I still have no idea on how to calculate the value of a subexpression (subtree) without using an auxiliary stack .

I don't understand what your problem really is. If it is what you said initially, that doesn't require computing the value of a subexpression at all.

(3/2/5) means (3/2)/5, at least in C/C++. So if you want it to mean something else, you need to tell us what conventions you are using. The correct RPN for (3/(2/5)) is "3 2 5 / /". You can't do the type of manipulation that you were doing (and where did the division by 1 come from?).

[ventsyv]

I think he is having a problem with how exactly to build the tree from the expression ? Is that it ??

[Seeker]

Well, no, not really.

Unfortunately, I still have no idea on how to calculate the value of a subexpression (subtree) without using an auxiliary stack .

My problem is obvious. I have to calculate the value of the subexpression without using some auxiliary data structures (e.g. stack). How can I achieve that? Is it possible? Well, I guess it is, somehow... but is that next to impossible?