fan
11-04-2006, 08:00 AM
Hello all!
I have this small project for my Data Structures laboratory.
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.
I have this small project for my Data Structures laboratory.
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.