Postfix to Prefix Conversion using Stack Data Structure (With C++ Program Code)
In this tutorial we will convert in Postfix Expression to a Prefix Expression using Stack Data structure. We will understand the Rules to convert a Postfix expression to Prefix expression and also understand the pseudocode. Lastly we will write a C++ program to perform Postfix to Prefix expression conversion.
Rules for Postfix to Prefix using stack DS –
- Scan POSTFIX expression from LEFT to RIGHT
- IF the incoming symbol is a OPERAND, PUSH it onto the Stack
- IF the incoming symbol is a OPERATOR, POP 2 OPERANDs from the Stack, ADD this incoming OPERATOR in before the 2 OPERANDs & PUSH this whole new expression string back into the Stack.
- At the end POP and PRINT the full PREFIX expression from the Stack.
PSEUDOCODE –
C++ Program to Prefix to Infix Conversion using Stack DS –
#include<iostream> #include<stack> using namespace std; bool isOperand(char c) { if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { return true; } else { return false; } } string PostfixToPrefix(string postfix) { stack < string > s; for (int i = 0; i < postfix.length(); i++) { if (isOperand(postfix[i])) { string op(1, postfix[i]); s.push(op); } else { string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); s.push(postfix[i] + op2 + op1); } } return s.top(); } int main() { string prefix, postfix; cout << "Enter a POSTFIX Expression :" << endl; cin >> postfix; cout << "POSTFIX EXPRESSION: " << postfix << endl; prefix = PostfixToPrefix(postfix); cout << endl << "PREFIX EXPRESSION: " << prefix; return 0; }