CODEWITHSUNDEEP
c++algorithmparsing
jmasterx
jmasterx

Reputation: 54113

Adding parenthesis around an expression with a '-(inner expression)'

I currently have a function that tokenizes infix expressions.

However, I have 1 little issue.

Say for example I have:

2 ^ -(5 * 5)

This gets converted to:

2
^
-1
*
(
5
*
5
)

However this does not evaluate to what I want.

My goal is to wrap it in parenthesis:

2
^
(
-1
*
(
5
*
5
)
)

This would evaluate exactly as I need it.

What could I do to get this output. A stack based approach is fine.

Given that I have an array of tokens like seen above, how could I get a new array with the negation wrapped in parenthesis?

If necessary, I can modify my code to generate the following without the -1 *:

2
^
-
(
5
*
5
)

What would be the algorithm to add the parenthesis so that negatives are properly evaluated?

Thanks

Upvotes: 1

Views: 221

Answers (2)

Chris J. Kiick
Chris J. Kiick

Reputation: 1505

If you are using the shunting yard algorithm, then it's not that hard. The first thing to realize is that you are dealing with two different operators, both of which use the '-' symbol. One is the "subtract" operator, and the other is the "negate" operator.

The trick is how to tell them apart. When you see '-', look at the previous symbol. If it was null (the '-' is at the beginning of the string), an operator or an open parenthesis, then it's the negate operator. Otherwise it's subtract.

Each operator has a precedence and associativity, which you have to know ahead of time in order to implement shunting-yard. The subtract operator has precedence below multiply and divide and is left associative. The precedence of negation is between multiply and exponent, and it's right associative. It also only takes 1 operand instead of 2.

So your expression, after conversion, would be: 2 5 5 * negate ^

Ok, great, but what if "negate" does not compute? That's ok, pop the negate and push -1 * in it's place. Now you have 2 5 5 * -1 * ^. Or, if you don't do negative numbers, replace that '-' with "0 1 -" to get "2 5 5 * 0 1 - * ^".

Upvotes: 1

Sean
Sean

Reputation: 62472

You can always parse it to reverse polish notation and then just evaluation the stream. This would give you a stream of:

2 -1 5 5 * * ^

As you traverse the stream from left to right you push the operands (2, 5, etc) onto a stack. When you encounter an operator (*, ^) you pop the appropriate number of operands off the stack, perform the operation and then push the result onto the stack. At then end you'll have on value on the stack, which will be the result.

Alternatively you can treat unary minus as a different operator from regular minus. The unary minus will have a higher priority than regular operators:

2 5 5 * unary- ^

Upvotes: 1

Related Questions