Need to support for unary operator in postfix evaluation.

[amirsoroush]

Feature description

As mentioned in #8724, we have two files for evaluating postfix expressions. But currently both of them only work with binary operators and will raise an exception when an unary operator is given.

example:

>>> res = evaluate_postfix(["2", "-", "3", "+"])
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File ".../stacks/evaluate_postfix_notations.py", line 31, in evaluate_postfix
 b, a = stack.pop(), stack.pop()
IndexError: pop from empty list
>>> 

2-3+ is a postfix notation for -2+3 infix and should result in 1.

[tianyizheng02]

I think there are three main ways that we can implement this, but none of them is a perfect solution:

1. We could distinguish (unary) negation operators from (binary) subtraction operators, perhaps by using different symbols for each. Otherwise, the algorithm would treat all negative signs as subtraction and try to pop two operands off the stack when it should only pop one (which is what it currently does). Of course, it's inconvenient to force users to make this distinction when entering input.
2. We could sidestep negation operators entirely by always having 0 - x instead of -x. Thus, we'd have 02-3+ for 0-2+3, which would correctly evaluate to 1 using the current algorithm. Of course, this would also be inconvenient to enforce.
3. We could try to disambiguate negation from subtraction using the contents of the stack. For instance, 2-3+ raises an exception because the algorithm thinks that the - is subtraction and tries to pop two operands from the stack when there's only one. To fix this, we could have it so that - is treated as negation when there's only one operand on the stack. There may be edge cases where this doesn't work, but I'm not sure.

Let me know if you've thought of any other potential solutions.

[niranjank2022]

Can you please say how it would be inconvenient to enforce 2.? We can insert 0 at the beginning of the string if the first character is not a number and continue the postfix conversion, can't we? Or am I wrong?

[amirsoroush]

I think there are three main ways that we can implement this, but none of them is a perfect solution:

1. We could distinguish (unary) negation operators from (binary) subtraction operators, perhaps by using different symbols for each. Otherwise, the algorithm would treat all negative signs as subtraction and try to pop two operands off the stack when it should only pop one (which is what it currently does). Of course, it's inconvenient to force users to make this distinction when entering input.
2. We could sidestep negation operators entirely by always having 0 - x instead of -x. Thus, we'd have 02-3+ for 0-2+3, which would correctly evaluate to 1 using the current algorithm. Of course, this would also be inconvenient to enforce.
3. We could try to disambiguate negation from subtraction using the contents of the stack. For instance, 2-3+ raises an exception because the algorithm thinks that the - is subtraction and tries to pop two operands from the stack when there's only one. To fix this, we could have it so that - is treated as negation when there's only one operand on the stack. There may be edge cases where this doesn't work, but I'm not sure.

Let me know if you've thought of any other potential solutions.

For the same reason you mentioned, I'm not satisfied with the first option as we normally do not differentiate between unary minus and binary minus operator in a math expression. I think last option is reasonable and it's what @rohan472000 has suggested in #8758 .

[tianyizheng02]

Can you please say how it would be inconvenient to enforce 2.? We can insert 0 at the beginning of the string if the first character is not a number and continue the postfix conversion, can't we? Or am I wrong?

@niranjank2022 We're not converting the string to postfix notation. Rather, this file evaluates a postfix string, so the input is already in postfix notation, not infix notation. If there's a unary negation operator, it definitely won't be at the start of the string, so it's not immediately obvious where to insert the 0.

[tianyizheng02]

I think there are three main ways that we can implement this, but none of them is a perfect solution:

1. We could distinguish (unary) negation operators from (binary) subtraction operators, perhaps by using different symbols for each. Otherwise, the algorithm would treat all negative signs as subtraction and try to pop two operands off the stack when it should only pop one (which is what it currently does). Of course, it's inconvenient to force users to make this distinction when entering input.
2. We could sidestep negation operators entirely by always having 0 - x instead of -x. Thus, we'd have 02-3+ for 0-2+3, which would correctly evaluate to 1 using the current algorithm. Of course, this would also be inconvenient to enforce.
3. We could try to disambiguate negation from subtraction using the contents of the stack. For instance, 2-3+ raises an exception because the algorithm thinks that the - is subtraction and tries to pop two operands from the stack when there's only one. To fix this, we could have it so that - is treated as negation when there's only one operand on the stack. There may be edge cases where this doesn't work, but I'm not sure.

Let me know if you've thought of any other potential solutions.

For the same reason you mentioned, I'm not satisfied with the first option as we normally do not differentiate between unary minus and binary minus operator in a math expression. I think last option is reasonable and it's what @rohan472000 has suggested in #8758 .

@amirsoroush I think option 3 is the most reasonable as well, but I'm not completely sure if this can always be generalized to other unary operators. I believe this method would also work for unary functions such as sin(x), but I'm not sure if this works for, for example, the factorial function x!.