Convert Prefix to Postfix

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
23 upvotes
Asked in company
Provakil

Problem statement

You are given a string ‘s’ of size ’n’, representing the prefix form of a valid mathematical expression.


Your task is to find out its corresponding postfix expression.


The expected time and space complexity is O(n) and O(n), where ‘n’ is the size of the string ‘s’.


Note: 
The only operators used in the expressions are ‘+’, ‘-’, ‘*’, ‘/’.


Example: 
Input: ‘n’ = 5, ‘s’ = “/A+BC”

Output: ABC+/

Explanation: For ‘s’ = “/A+BC”, the correct postfix expression is “ABC+/”.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line is an integer ‘n’, denoting the string ‘s’ size.
The second line contains a string ‘s’, denoting the prefix expression.


Output Format: 
Return a string representing the postfix form of the expression.


Note:- 
You don't need to print anything. Just implement the given function.
Sample Input 1:
5
/A+BC


Sample Output 1 :
ABC+/


Explanation Of Sample Input 1:
Input: ‘n’ = 5, ‘s’ = “/A+BC”

Output: ABC+/

Explanation: For ‘s’ = “/A+BC”, the correct postfix expression is “ABC+/”.


Sample Input 2:
9
-/A+BC*DE


Sample Output 2:
ABC+/DE*-


Explanation of sample output 2:
Input: ‘n’ = 9, ‘s’ = “-/A+BC*DE”

Output: ABC+/DE*-

Explanation: For ‘s’ = “-/A+BC*DE”, the correct postfix expression is “ABC+/DE*-”.


Constraints:
3 <= n < 10^4
The characters in ‘s’ are either one of {‘+’, ‘-’, ‘/’, ‘*’} or is one of the Uppercase Letters.

Time Limit: 1 sec
Hint

Can we use stack?

Approaches (1)
Stack

We can convert a prefix expression into a postfix expression using a stack. First, we will reverse the string and iterate through it. When we encounter an operand, we will push it into the stack. When meeting an operator ‘op’, we will pop two operands from the stack, ‘s1’ and ‘s2’. We will then push into the stack expression ‘s1’+’s2’+’op’, where + means concatenation. Ultimately, we will have our final expression as the only element in the stack.
 

The steps are as follows:
 

function preToPost(string s):

  1. Initialize stack ‘st’.
  2. Reverse string ‘s’.
  3. Initialize an empty array ‘o’, and insert ‘+’, ‘-’, ‘/’, and ‘*’ in the array.
  4. Iterate over the string ‘s’ using variable ‘i’:
    • Initialize a boolean variable ‘isOp’, and assign it to ‘false’.
    • Iterate over the array ‘o’ using variable ‘j’:
      • If ‘s[i] == o[j]’:
        • Assign ‘isOp’ to ‘true’.
    • Declare a string ‘cur’ and assign it to s[i]
    • if ‘isOp == false’:
      • Push ‘cur’ in the stack ‘st’.
    • else
      • Initialize a string ‘s1’ and assign it to ‘st.top()’.
      • Pop the top element of the stack, i.e., ‘st.pop()’.
      • Initialize a string ‘s2’ and assign it to ‘st.top()’.
      • Pop the top element of the stack, i.e., ‘st.pop()’.
      • Push ‘s1 + s2 + cur’ in the stack, i.e., ‘st.push(s1 + s2 + cur)’.
  5. Return the top of the stack, i.e., ‘st.top()’.
Time Complexity

O(n), where ‘n’ is the length of string ‘s’.


We are iterating over all the elements of string ‘s’; we push or pop a string from the stack in each iteration. This operation may take an O(n) time due to the length of the string being pushed or popped.
 

Hence, the time complexity is O(n).

Space Complexity

O(n), where ‘n’ is the length of string ‘s’.

 

We are storing a maximum of ‘n’ characters in the stack.


Hence, the space complexity is O(n).

Code Solution
(100% EXP penalty)
Convert Prefix to Postfix
Full screen
Console