Prefix To Infix Conversion In C++
By Anurag TiwariIn this tutorial, we shall learn the easiest way to convert prefix expression to infix expression in C++. As we know that we humans are more used to infix expressions such as ( a + b ) rather than prefix expression such as (+ a b). Contrary to that the computer finds it easy to understand prefix and postfix rather than infix.
The reason is, the easy and fast implementation of prefix and postfix expression. For the problem, we shall be using STL stack, as we require some Last In First Out data structure.
Algorithm and the convert function
Initially, the user inputs integer ‘n’ the total number of strings to be inputted, and the next n lines have prefix strings. We have also used a stack of string named ‘ch’ to store the operands. The for loop goes from rightmost end to beginning. The reason is that if we encounter an operand ( i.e. a variable) then it will be pushed into the stack but if any operator is encountered then two operands will be popped.
The first one stored in op1 and the next in op2. After that, the function convert is called which converts the prefix expression to infix part by part. The final infix expression is stored at the top of the stack. Below is our C++ code for Prefix To Infix Conversion:
#include <bits/stdc++.h>
typedef long long ll; // macro for long long
using namespace std;
string convert(string op1, string op, string op2); // Function to convert the value of part of expression
int main()
{
ll n; // User inputs n no of prefix expressions
cin >> n;
for (ll t = 0; t < n; t++)
{
string s;
cin >> s;
stack<string> ch;
for (ll i = s.length() - 1; i >= 0; i--)
{
if (s[i] == ',') // Condition to ignore comma
{
continue;
}
else if (isalpha(s[i])) // checks if character is operand(variable) or operator
{
string temp;
temp=temp+s[i]; // Convert char to const char*
ch.push(temp); // that is to covert character to string
}
else if (s[i] == '+' || (s[i] == '-' || (s[i] == '*' || (s[i] == '/'))))
{
string op1,op2,temp;
temp=temp+s[i]; // Convert char to const char*
op1 = ch.top();ch.pop();
op2 = ch.top();ch.pop();
string res = convert(op1,temp,op2);
ch.push(res);
}
}
cout << ch.top() << endl; // The top of stack holds the result
}
return 0;
}
string convert(string op1, string op, string op2){
if (op == "+")
return "("+ op1 + "+" + op2 + ")";
else if (op == "-")
return "("+ op1 + "-" + op2 + ")";
else if (op == "*")
return "("+ op1 + "*" + op2 + ")";
else if (op == "/")
return "("+ op1 + "/" + op2 + ")";
}For the input:
5 +,+,A,*,B,C,D *+AB+CD +*AB*CD +++ABCD *,+,A,B,C
The output is:
((A+(B*C))+D) ((A+B)*(C+D)) ((A*B)+(C*D)) (((A+B)+C)+D) ((A+B)*C)
You may observe the code that it is written so, as to ignore the comma also if the input string has some. We also have added a parenthesis to each sub-expression of the infix string for clarity. Hence we get the infix expression finally in order of their execution.
You may also like to learn:
Leave a Reply