Last Updated: 15 Jun, 2023

Convert Prefix to Postfix

Moderate

Asked in company

Solve now

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+/”.

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.

Solve now

Approaches

01 Approach

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):

Initialize stack ‘st’.
Reverse string ‘s’.
Initialize an empty array ‘o’, and insert ‘+’, ‘-’, ‘/’, and ‘*’ in the array.
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)’.
Return the top of the stack, i.e., ‘st.top()’.

Solve now

Convert Prefix to Postfix

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:

Example:

Input Format:

Output Format:

Note:-

Approaches

01 Approach

The steps are as follows: function preToPost(string s):

The steps are as follows:

function preToPost(string s):