Problem of the day
You are given a mathematical expression in postfix notation. The expression consists of alphabets(both lowercase and uppercase) and operators.
Convert this expression to infix notation.
Surround every expression with a pair of parentheses “()”.
Input: ‘postfix’ = “ab+c+”
Output: ‘infix’ = “((a+b)+c)”
Explanation: The expression ((a+b)+c)” in infix is equivalent to “ab+c+” in postfix.
The first line of the input contains the length of the postfix string.
The second line contains the string ‘postfix’, the expression in postfix notation. The expression is a valid postfix expression with at least two operands and one operator.
Return the expression in infix notation.
5
ab+c+
((a+b)+c)
The expression “((a+b)+c)” in infix is equivalent to “ab+c+” in postfix.
9
ABC/DA-*+
(A+((B/C)*(D-A)))
3 <= ‘postfix.length’ <= 10^4
In Postfix notation, the operators are written after the operands. What data structure can help you easily fetch the last two operands for each operator?
In postfix expression, the operands are followed by the operator. So if we encounter an operator, we’ll consider the latest two operands and evaluate them.
Algorithm:
O(‘N’ ^ 2), Where ‘N’ is the length of the string ‘postfix’.
We have a loop running ‘N’ times. Within the loop, we are performing an O(n) operation, the string concatenation, which is roughly O(n) as the length of the strings v2, postfix[i], and v1 combined, can be at most n.
Hence the time complexity is O(‘N’ ^ 2).
O(‘N’), Where ‘N’ is the length of the string ‘postfix’.
Ultimately, we store the entire expression in the stack before returning it.
Hence the space complexity is O(‘N’).
Interview problems
Easy C++ solution
string postToInfix(string s) {
// Write your code here.
int n = s.size();
stack<string>st;
for(int i = 0; i< n; i++){
if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' &&
s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9'))
st.push(string(1,s[i]));
else{
string s1 = st.top();
st.pop();
string s2 = st.top();
st.pop();
st.push('(' + s2 + s[i] + s1 + ')');
}
}
return st.top();
}
Interview problems
Mistmatch in input/output format
My java code: import java.util.Stack;
public class Solution {
public static String postToInfix(String postfix) {
// Write your code here.
Stack<String> s=new Stack<>();
for(int i=0;i<postfix.length();i++){
char c =postfix.charAt(i);
String ch=Character.toString(c);
if(Character.isLetterOrDigit(c)){
s.push(ch);
} else {
if(!s.isEmpty()){
String secOp = s.pop();
String firstOp= s.pop();
String res = '('+firstOp+ch+secOp+')';
s.push(res);
}
}
}
String result="";
while(!s.isEmpty()){
result=s.pop();
}
return result;
}
}
Interview problems
Java Wrong Output format!!
Input provided is :
5
ab+c+
for output, it is taking 5 as the string instead of ab+b+,
resulting in 5 as the answer.
Interview problems
Getting Wrong Answer in Sample Test Case?
I also faced the same problem again and again. Maybe there are some internal issue in executing those sample test case. My code is running fine in VS code and returning also the correct answer but when I copy-paste the same code here its shows Wrong answer in sample Test cases.
Interview problems
Postfix to Infix Best Approach in CPP
string postToInfix(string s) {
// Write your code here.
stack<string> st;
string ans;
for(int i=0;i<s.size();i++){
if((s[i]>='A' && s[i]<='Z')||(s[i]>='a' && s[i]<='z')){
st.push(string(1,s[i]));
}else{
string s1=st.top();
st.pop();
string s2=st.top();
st.pop();
string temp='('+s2+s[i]+s1+')';
st.push(temp);
}
}
while(!st.empty()){
ans=ans+st.top();
st.pop();
}
return ans;
}// Please upvote if this helped
// It will help me,Thank you
Interview problems
test case is running all correct in custom test case if i put it there manually ,but in sample test case always showing runtime error'b
problem in platform
Interview problems
Python easy
def postToInfix(postfix: str) -> str:
# Write your code here.
st=[]
for i in postfix:
if i.isalnum(): #Operand
st.append(i)
else: #operator
op2=st.pop()
op1=st.pop()
result= "("+op1+i+op2+")"
st.append(result)
return st[0]
pass
Interview problems
Output format is wrong
Maybe there is some issue with the output format in java as it is printing the length of the result string while it's working fine on VS code.
import java.util.Stack;
public class Solution {
public static String postToInfix(String p) {
// Write your code here.
Stack<String> st = new Stack<>();
int n = p.length();
for(int i = 0; i < n; i++){
char c = p.charAt(i);
if(Character.isLetterOrDigit(c)) st.push(Character.toString(c));
else{
if(st.size() > 1){
String b = st.pop();
String a = st.pop();
String res = "(" + a + c + b + ")";
st.push(res);
}
}
}
return st.pop();
}
}Interview problems
Postfix to Infix || C++ || O(n) solution
string postToInfix(string s) {
// Write your code here.
stack<string> st;
string ans;
for(int i=0;i<s.size();i++){
if((s[i]>='A' && s[i]<='Z')||(s[i]>='a' && s[i]<='z')){
st.push(string(1,s[i]));
}else{
string s1=st.top();
st.pop();
string s2=st.top();
st.pop();
string temp='('+s2+s[i]+s1+')';
st.push(temp);
}
}
while(!st.empty()){
ans=ans+st.top();
st.pop();
}
return ans;
}
All tags 
Sort by