|
| 1 | + |
| 2 | + |
| 3 | +/* |
| 4 | +Contributer: |
| 5 | + Github Username: ultimatecoder2 |
| 6 | + Name: Deepanshu Jindal |
| 7 | +*/ |
| 8 | + |
| 9 | +/* |
| 10 | + Problem: Converting an infix expression to postfix expression |
| 11 | +
|
| 12 | +
|
| 13 | + Approach: Here we will make a stack that will store operators. |
| 14 | + If stack is empty, then we willpush operator in stack |
| 15 | + Now when the precedence of the operator on the top of the stack is greater than the new encountered operator then we pop the operator and insert it to the postfix string. Then we push the newly encountered one operator into stack. |
| 16 | + else we just insert the operator in the stack. |
| 17 | + Now Whenever we encounter an opening parantheses then we just insert it in the stack as acc to BoadMass rule, brackets should be solved first. |
| 18 | +
|
| 19 | + If we encounter a closing paranthesses i.e. ')' then we pop all the operators till we encountered a '('. |
| 20 | +
|
| 21 | + Sample Case 1: 3+5*3 |
| 22 | + Soln 1:353*+ |
| 23 | + Sample Case 2: 3*9-8 |
| 24 | + Soln 1:39*8- |
| 25 | +
|
| 26 | +*/ |
| 27 | +#include<bits/stdc++.h> |
| 28 | +using namespace std; |
| 29 | +bool isoperator(char ch) |
| 30 | +{ |
| 31 | + //returns true if we get an operator |
| 32 | + if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^') |
| 33 | + return 1; |
| 34 | + else |
| 35 | + return 0; |
| 36 | +} |
| 37 | + |
| 38 | +bool checkPrecedence(char op1,char op2) |
| 39 | +//Here op1 and op2 are 2 operators. |
| 40 | +//We return 1 if precedence of op2 > precedence of op1 |
| 41 | +{// We know precedence '(' < '+','-' <' *', '/' < '^' < ')' |
| 42 | + if(op2=='(') |
| 43 | + { |
| 44 | + return(0); |
| 45 | + } |
| 46 | + else |
| 47 | + { |
| 48 | + if(op1=='+'||op1=='-') |
| 49 | + {return(1);}//if precedence of incoming is less or equal |
| 50 | + else if(op1=='*'||op1=='/') |
| 51 | + { |
| 52 | + if(op2=='+'||op2=='-') |
| 53 | + return(0); |
| 54 | + else |
| 55 | + return(1);//if precedence of incoming is less or equal |
| 56 | + } |
| 57 | + else |
| 58 | + { |
| 59 | + if(op2=='^') |
| 60 | + return(1); |
| 61 | + else |
| 62 | + return (0); |
| 63 | + } |
| 64 | + } |
| 65 | +} |
| 66 | + |
| 67 | +int main() |
| 68 | +{ |
| 69 | + stack<char> operatorStack; |
| 70 | + string postfix="",infix; |
| 71 | + int len; |
| 72 | + bool IsOperator,isGreaterPrecedence; |
| 73 | + cout<<"Enter Infix string"<<endl; |
| 74 | + cin>>infix; |
| 75 | + len=infix.length(); |
| 76 | + |
| 77 | + for(int i=0;i<len;i++) |
| 78 | + { |
| 79 | + //Check for each element in the infix string and perform the required steps as per discussed approach |
| 80 | + if(infix[i]=='(')//Directly push to stack |
| 81 | + operatorStack.push('('); |
| 82 | + else if(infix[i]==')') |
| 83 | + { |
| 84 | + // pop all the operators till we encountered a '(' |
| 85 | + while((operatorStack.top()!='(')) |
| 86 | + { |
| 87 | + postfix+=operatorStack.top(); |
| 88 | + operatorStack.pop(); |
| 89 | + } |
| 90 | + operatorStack.pop(); |
| 91 | + } |
| 92 | + else |
| 93 | + { |
| 94 | + IsOperator=isoperator(infix[i]); |
| 95 | + if(IsOperator==0) |
| 96 | + { |
| 97 | + //As not an operator. So add it to postfix string |
| 98 | + postfix+=infix[i]; |
| 99 | + } |
| 100 | + else |
| 101 | + { |
| 102 | + |
| 103 | + if(operatorStack.empty()) |
| 104 | + operatorStack.push(infix[i]); |
| 105 | + else |
| 106 | + { |
| 107 | + //Here we check precedence |
| 108 | + isGreaterPrecedence=checkPrecedence(infix[i],operatorStack.top()); |
| 109 | + if(isGreaterPrecedence==1) |
| 110 | + { //Here precedence of |
| 111 | + while(isGreaterPrecedence==1 && operatorStack.empty()==0 && (operatorStack.top()!='('))//if precedence of incoming is less or equal |
| 112 | + { |
| 113 | + postfix+=operatorStack.top(); |
| 114 | + operatorStack.pop(); |
| 115 | + if(!operatorStack.empty()) |
| 116 | + isGreaterPrecedence=checkPrecedence(infix[i],operatorStack.top()); |
| 117 | + } |
| 118 | + } |
| 119 | + operatorStack.push(infix[i]); |
| 120 | + } |
| 121 | + } |
| 122 | + } |
| 123 | + } |
| 124 | + |
| 125 | + //If any operator left in stack then we add it to the end of the string |
| 126 | + while(!operatorStack.empty()) |
| 127 | + { |
| 128 | + if(operatorStack.top()!='(') |
| 129 | + postfix+=operatorStack.top(); |
| 130 | + operatorStack.pop(); |
| 131 | + } |
| 132 | + cout<<postfix<<endl; |
| 133 | + return 0; |
| 134 | +} |
0 commit comments