Postfix to Prefix Conversion in C++
In this tutorial, we will learn Postfix to Prefix Conversion in C++.
Postfix: If the operator appears in the expression after the operands, then it is called a postfix expression. For example-
AB+CD-*
Prefix: If the operator appears in the expression before the operands, then it is called a prefix expression.
*+AB-CD
Infix: It is a normal regular expression with the correct order of operands and operators.
(A+B) * (C-D)
Postfix to Prefix Conversion in c++
We will first convert the expression from postfix to infix and then infix to the prefix. This will be easy to do for us.
Here is the dry run for it:
Here, is the code implementation:
#include <bits/stdc++.h> using namespace std; bool isOperator(char x) { if(x=='+'||x=='-'||x=='/'||x=='*') return true; return false; } string postToPre(string post_exp) { stack<string> s; int lengthofstring = post_exp.size(); for (int p = 0; p < lengthofstring; p++) { // check if symbol is operator if (isOperator(post_exp[p])) { // pop two operands from stack string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); // concat the operands and operator string temp = post_exp[p] + op2 + op1; // Push string temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(string(1, post_exp[p])); } } //stack[0] contains the Prefix expression return s.top(); } int main() { string post_exp = "ABC/-AK/L-*"; cout << "Prefix : " << postToPre(post_exp); return 0; }
Output:
Prefix : *-A/BC-/AKL
Also, refer to:
Count the number of occurrences of an element in a linked list in C++
Thank you! Please comment for suggestions.
Leave a Reply