Prefix to Postfix Conversion
Medium
Given an expression in prefix notation, convert it to postfix notation. In prefix notation, an operator is placed before its operands, while in postfix notation, the operator is placed after its operands.
Example 1
Input
[ "*+AB-CD" ]
Output
AB+CD-*
Explanation. The prefix expression '* + A B - C D' converts to the postfix expression 'A B + C D - *'.
Example 2
Input
[ "+A*BC" ]
Output
ABC*+
Explanation. The prefix expression '+ A * B C' converts to the postfix expression 'A B C * +'.
Example 3
Input
[ "-+7*45+20" ]
Output
745*+20+-
Explanation. The prefix expression '- + 7 * 4 5 + 2 0' converts to the postfix expression '7 4 5 * + 2 0 + -'.
Follow-up: Can you optimize your solution to run in linear time complexity?
Constraints:
The input string will only contain single-digit integers and operators `+`, `-`, `*`, and `/`. The string will be a valid prefix expression.
- Views
- 11