Disclaimer: No, this is not a joke challenge to reverse a string.
There is only one operation to support: subtraction (
You also only have two atoms to support: zero (
0) and one (
Here, the prefix notation
-AB is equivalent to the postfix notation
B are expressions.
Your task is to (recursively) convert an expression in prefix notation to its equivalent in postfix notation.
An expression in prefix notation is generated by the following grammar:
S > -SS S > 0 S > 1
An expression in postfix notation is generated by the following grammar:
S > SS- S > 0 S > 1
Prefix notation: --01-0-01 Parentheses: -(-01)(-0(-01)) Convert: (01-)(0(01-)-)- Postfix notation: 01-001---
Rules and freedom
- You may rename the operation and the atoms to whichever character, as long as it is consistent.
- The input format must be consistent with the output format (apart from the fact that the input is in prefix notation and the output is in postfix notation).
Input Output 1 1 0 0 -01 01- -10 10- --01-0-01 01-001---
Testcases credits to Dada.