const71
asked on
Need code that adds brackets to multi-leveled expressions (group by indentation levels)
I need a simple and elegant algorithm that will add properly
positioned brackets between 2 or more multi-leveled expressions.
The diagram below shows exactly what I am looking for:
!! NOTE: VIEW IN FIXED FONT SUCH AS COURIER NEW!!
==========================
8 POSSIBLE SCENARIOS FOR 3 EXPRESSIONS USING UP TO 2 LEVELS
==========================
(1) (2) (3) (4) (5) (6) (7) (8)
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
GROUP LEVEL: |1|2| |1|2| |1|2| |1|2| |1|2| |1|2| |1|2| |1|2|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION A: |A| | |A| | |A| | |A| | | |A| | |A| | |A| | |A|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION B: |B| | |B| | | |B| | |B| |B| | |B| | | |B| | |B|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION C: |C| | | |C| |C| | | |C| |C| | | |C| |C| | | |C|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
==========================
BRACKET SOLUTIONS FOR THE 8 SCENARIOS SHOWN ABOVE
==========================
(1) A + B + C
(2) A + B + (C)
(3) A + (B) + C
(4) A + (B + C)
(5) (A) + B + C
(6) (A) + B + (C)
(7) (A + B) + C
(8) (A + B + C)
Things become more complicated as we add more levels and
expressions. Is there an elegant approach?.
Thanks
positioned brackets between 2 or more multi-leveled expressions.
The diagram below shows exactly what I am looking for:
!! NOTE: VIEW IN FIXED FONT SUCH AS COURIER NEW!!
==========================
8 POSSIBLE SCENARIOS FOR 3 EXPRESSIONS USING UP TO 2 LEVELS
==========================
(1) (2) (3) (4) (5) (6) (7) (8)
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
GROUP LEVEL: |1|2| |1|2| |1|2| |1|2| |1|2| |1|2| |1|2| |1|2|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION A: |A| | |A| | |A| | |A| | | |A| | |A| | |A| | |A|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION B: |B| | |B| | | |B| | |B| |B| | |B| | | |B| | |B|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
EXPRESION C: |C| | | |C| |C| | | |C| |C| | | |C| |C| | | |C|
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
==========================
BRACKET SOLUTIONS FOR THE 8 SCENARIOS SHOWN ABOVE
==========================
(1) A + B + C
(2) A + B + (C)
(3) A + (B) + C
(4) A + (B + C)
(5) (A) + B + C
(6) (A) + B + (C)
(7) (A + B) + C
(8) (A + B + C)
Things become more complicated as we add more levels and
expressions. Is there an elegant approach?.
Thanks
ASKER
I know that, but i need code that does this for me. I have some Visual Basic code as a starting point if that will help...
ASKER
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> if left has a " ( " then
>> find first " ) " from the end (of hte left part), split in between
>> left = evaluate( left->left, left->right, left->op )
sorry, I should indicate that you need to do the same for the right side :) This forms an expression tree:
X = A + ( B + (C + D) )
Gives
X
/ \
/ \
/ \
A +
/ \
/ \
/ \
B +
/ \
/ \
/ \
C D
as you can see, each node either has 2 children or none - nodes with two children are operators and nodes with none are operands. This binary tree allows for some efficient login operations, so you don't have to limit yourself to recursion. If it were me, I'd use a stack.
>> find first " ) " from the end (of hte left part), split in between
>> left = evaluate( left->left, left->right, left->op )
sorry, I should indicate that you need to do the same for the right side :) This forms an expression tree:
X = A + ( B + (C + D) )
Gives
X
/ \
/ \
/ \
A +
/ \
/ \
/ \
B +
/ \
/ \
/ \
C D
as you can see, each node either has 2 children or none - nodes with two children are operators and nodes with none are operands. This binary tree allows for some efficient login operations, so you don't have to limit yourself to recursion. If it were me, I'd use a stack.
ASKER
great! thanks
In your sample with 8 possibilities, the possible combinations are equal to 2^3 (two levels of three expressions).
You can also think of your expressions as binary numbers:
1. 000
2. 001
3. 010
4. 011
5. 100
6. 101
7. 110
8. 111
The pattern is everywhere there are sequences of 1, you'll need to put parentheses around things.