Skip to content

Need to support for unary operator in postfix evaluation. #8754

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
amirsoroush opened this issue May 20, 2023 · 5 comments · Fixed by #8787
Closed

Need to support for unary operator in postfix evaluation. #8754

amirsoroush opened this issue May 20, 2023 · 5 comments · Fixed by #8787
Labels
enhancement This PR modified some existing files

Comments

@amirsoroush
Copy link
Contributor

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.

@amirsoroush amirsoroush added the enhancement This PR modified some existing files label May 20, 2023
@tianyizheng02
Copy link
Contributor

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
Copy link

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
Copy link
Contributor Author

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
Copy link
Contributor

tianyizheng02 commented May 28, 2023

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
Copy link
Contributor

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!.

cclauss added a commit that referenced this issue Aug 23, 2023
* Updated postfix_evaluation.py to support Unary operators and floating point numbers Fixes #8754 and #8724

Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py

Signed-off-by: Arijit De <[email protected]>

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated postfix_evaluation.py to support Unary operators and floating point numbers. Fixes #8754 and formatted code to pass ruff and black test.

Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes #8724 and made sure it passes doctest

Signed-off-by: Arijit De <[email protected]>

* Fixed return type hinting required by pre commit for evaluate function

Signed-off-by: Arijit De <[email protected]>

* Changed line 186 to return only top of stack instead of calling the get_number function as it was converting float values to int, resulting in data loss. Fixes #8754 and #8724

Signed-off-by: Arijit De <[email protected]>

* Made the requested changes

Also changed the code to make the evaluate function first convert all the numbers and then process the valid expression.

* Fixes #8754, #8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes #8724. Added a doctest example with unary operator.

* Fixes #8754, #8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes #8724. Added a doctest example with unary operator.

* Fixes #8754, #8724 Updated the parse_token function of postfix_evaluation.py

ostfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes #8724. Added a doctest example with unary operator and invalid expression.

* Fixes #8754, #8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes #8724. Added a doctest example with unary operator and invalid expression.

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

---------

Signed-off-by: Arijit De <[email protected]>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <[email protected]>
sedatguzelsemme pushed a commit to sedatguzelsemme/Python that referenced this issue Sep 15, 2024
…ms#8787)

* Updated postfix_evaluation.py to support Unary operators and floating point numbers Fixes TheAlgorithms#8754 and TheAlgorithms#8724

Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py

Signed-off-by: Arijit De <[email protected]>

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated postfix_evaluation.py to support Unary operators and floating point numbers. Fixes TheAlgorithms#8754 and formatted code to pass ruff and black test.

Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes TheAlgorithms#8724 and made sure it passes doctest

Signed-off-by: Arijit De <[email protected]>

* Fixed return type hinting required by pre commit for evaluate function

Signed-off-by: Arijit De <[email protected]>

* Changed line 186 to return only top of stack instead of calling the get_number function as it was converting float values to int, resulting in data loss. Fixes TheAlgorithms#8754 and TheAlgorithms#8724

Signed-off-by: Arijit De <[email protected]>

* Made the requested changes

Also changed the code to make the evaluate function first convert all the numbers and then process the valid expression.

* Fixes TheAlgorithms#8754, TheAlgorithms#8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes TheAlgorithms#8724. Added a doctest example with unary operator.

* Fixes TheAlgorithms#8754, TheAlgorithms#8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes TheAlgorithms#8724. Added a doctest example with unary operator.

* Fixes TheAlgorithms#8754, TheAlgorithms#8724 Updated the parse_token function of postfix_evaluation.py

ostfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes TheAlgorithms#8724. Added a doctest example with unary operator and invalid expression.

* Fixes TheAlgorithms#8754, TheAlgorithms#8724 Updated postfix_evaluation.py

postfix_evaluation.py now supports Unary operators and floating point numbers.
Also merged evaluate_postfix_notations.py and postfix_evaluation.py into postfix_evaluation.py which fixes TheAlgorithms#8724. Added a doctest example with unary operator and invalid expression.

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

* Update postfix_evaluation.py

---------

Signed-off-by: Arijit De <[email protected]>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement This PR modified some existing files
Projects
None yet
4 participants
@tianyizheng02 @niranjank2022 @amirsoroush and others