-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathInfix to postix.cpp
90 lines (86 loc) · 2.1 KB
/
Infix to postix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<string>
#include<iostream>
#include<stack>
#include<ctype.h>
using namespace std;
int GetOperatorWeight(char op)
{ /*Assign Weights to operators*/
int weight = -1;
switch(op)
{
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
case '^':
weight = 3;
break;
}
return weight;
}
int higherprecedence(char op1 , char op2)
{ /*Compares two operands, returns on with larger weight*/
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
return (op1Weight>= op2Weight ? 1:0);
}
string itp(string exp)
{ /*function that converts infix to postfix*/
int i;
stack<char> S;
string res;
res.clear();
for(i=0;i<exp.length();i++)
{ //Iterates over characters
char ch=exp[i];
if(ch=='('){
S.push(ch);
}
else if(ch==')')
{
while(!S.empty() && S.top()!='(')
{ //Pop and add to result till '(' encountered, or stack empty
res += ' ';
res+=S.top();
S.pop();
}
S.pop(); //Pop to remove '('
}
else if(GetOperatorWeight(ch) == -1){ //Add to result if not a supported operand
res += ch;
}
else if(S.empty() || higherprecedence(S.top(),ch)==0){
S.push(ch); //Push on empty stack or if ch precedes top element
res += ' ';
}
else if(higherprecedence(S.top(),ch)==1)
{ //Pop till '(' or lower precedence operand encountered, or stack empty
while(!S.empty() && higherprecedence(S.top(),ch)==1 && S.top()!='('){
res += ' ';
res+=S.top();
S.pop();
}
S.push(ch); //Push new operand
res += ' ';
}
}
while(!S.empty())
{ //To empty stack after expression iteration completed
res += ' ';
res+=S.top();
S.pop();
}
return res;
}
int main(){
cout << "This program converts infix expression to postfix expression\n";
string exp;
cout << "Enter an infix expression :";
cin >> exp;
string postfix = itp(exp);
cout << "Output = " << postfix << "\n";
}