Skip to content

Instantly share code, notes, and snippets.

@ms1797
Forked from mycodeschool/InfixToPostfix.cpp
Last active September 11, 2022 11:43
Show Gist options
  • Save ms1797/982b11b310a521367c5fd83de81d2851 to your computer and use it in GitHub Desktop.
Save ms1797/982b11b310a521367c5fd83de81d2851 to your computer and use it in GitHub Desktop.
Infix to Postfix conversion in C++ using stack. We are assuming that both operators and operands in input will be single character.
/*
Infix to postfix conversion in C++
Input Postfix expression must be in a desired format.
Operands and operator, both must be single character.
Only '+' , '-' , '*', '/' and '^' (for exponentiation) operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to convert Infix expression to postfix
string InfixToPostfix(string expression);
// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);
// Function to verify whether a character is alphanumeric chanaracter
//(letter or numeric digit) or not.
bool IsOperand(char C);
// Function to check whether a char is an opening parenthesis i.e '(' or '{' or '['
bool IsOpeningParentheses(char C);
// Function to check whether a char is an closing parenthesis i.e ')' or '}' or ']'
bool IsClosingParentheses(char C);
int main()
{
string expression;
cout<<"Enter Infix Expression \n";
getline(cin,expression);
string postfix = InfixToPostfix(expression);
cout<<"Output = "<<postfix<<"\n";
}
// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<char> S;
string postfix = ""; // Initialize postfix as empty string.
for(int i = 0;i< expression.length();i++) {
// Scanning each character from left.
// If character is a delimiter, move on.
if(expression[i] == ' ' || expression[i] == ',') continue;
// Else if character is an operand then just append it in res string
else if(IsOperand(expression[i]))
{
postfix +=expression[i];
}
//If character is operator, check for Higher precedence operator in Stack top
//till first opening bracket and pop all such operators
//Finally push the current operator on the Stack
else if(IsOperator(expression[i]))
{
while(!S.empty() && !IsOpeningParentheses(S.top())
&& HasHigherPrecedence(S.top(),expression[i]))
{
postfix+= S.top();
S.pop();
}
S.push(expression[i]);
}
//If opening Parentheses simply push it on the Stack
else if(IsOpeningParentheses(expression[i]))
{
S.push(expression[i]);
}
//If Closing Parentheses then pop all the operators and append to res string
// until Stack top is opening Parentheses and finally one extra pop for Opening Parentheses
else if(IsClosingParentheses(expression[i]))
{
while(!S.empty() && !IsOpeningParentheses(S.top())) {
postfix += S.top();
S.pop();
}
S.pop();
}
}
//Finally pop and append all operators till Stack is not empty
while(!S.empty()) {
postfix += S.top();
S.pop();
}
return postfix;
}
// Function to verify whether a character is english letter or numeric digit.
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C)
{
if(C >= '0' && C <= '9') return true;
if(C >= 'a' && C <= 'z') return true;
if(C >= 'A' && C <= 'Z') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^')
return true;
return false;
}
bool IsOpeningParentheses(char C)
{
if(C == '(' || C == '{' || C=='[')
return true ;
return false;
}
bool IsClosingParentheses(char C)
{
if(C == ')' || C == '}' || C==']')
return true ;
return false;
}
// Function to verify whether an operator is right associative or not.
int IsRightAssociative(char op)
{
if(op == '^') return true;
return false;
}
// Function to get weight of an operator. An operator with higher weight will have higher precedence.
int GetOperatorWeight(char op)
{
int weight = -1;
switch(op)
{
case '+':
case '-':
weight = 1;
break ;
case '*':
case '/':
weight = 2;
break ;
case '^':
weight = 3;
}
return weight;
}
// Function to perform an operation and return output.
int HasHigherPrecedence(char op1, char op2)
{
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
// If operators have equal precedence, return true if they are left associative.
// return false, if right associative.
// if operator is left-associative, left one should be given priority.
if(op1Weight == op2Weight)
{
if(IsRightAssociative(op1)) return false;
else return true;
}
return op1Weight > op2Weight ? true: false;
}
@kaushiks90
Copy link

// Function to verify whether an operator is right associative or not.
int IsRightAssociative(char op)
{
if(op == '^') return true;
return false;
}

Return should be bool

@kaushiks90
Copy link

case '^':
weight = 3;
}
break missing

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment