-
Notifications
You must be signed in to change notification settings - Fork 0
/
PostFixConverter.cpp
145 lines (129 loc) · 3.15 KB
/
PostFixConverter.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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<iostream>
using namespace std;
// ########################## Main Logic of the Code ########################## //
/*
==> Take data as a String
==> Read it Character by Character
==> If the char is '(' then push it to the Stack
==> If the char is ')' then Pop until u get ')'
==> If the char is Operand then just simply append it to another string/result
==> for operator check if input character's priority > the element in the stack then push it the character to the stack
==> if the given input priority < the element in the Stack[top] then first Pop the element and then push it to the stack
==> Pop the remaining elements
*/
// ########################################## Global Declarations ############################################## //
int const size = 20;
char Stack [size];
int top = -1;
//################################### Function Prototypes ############################################## //
string inFixToPostFixConverter(string exp);
int Priority(char ch);
// ############################################## Methods ############################################## //
char Push(char value)
{
if (top == size -1)
{
cout<<"Stack overflow\n";
return 0;
}
else
{
top++;
Stack[top] = value;
}
return value;
}
char Pop()
{
char temp = 0;
if(top == -1)
{
cout<<"Stack is Empty\n";
return temp;
}
else
{
temp = Stack[top];
top--;
}
return temp;
}
// ############################################### Main ################################################## //
int main()
{
string exp;
cout<<"Enter the infix Expression\n";
cin>>exp;
string result = inFixToPostFixConverter(exp);
cout<<"The Result in PostFix are \n"<<result;
}
// --------------------------------------------------------------------------------------------------------- //
string inFixToPostFixConverter(string exp)
{
string postFix;
for(int i=0; i<exp.length(); i++)
{
if(exp[i]=='(')
{
Push(exp[i]);
}
else if( exp[i]==')')
{
while((Stack[top] != '('))
{
postFix +=Pop();
}
Pop(); // pop the element
}
else if((exp[i] >= 'a' && exp[i] <= 'z') || (exp[i] >= 'A' && exp[i] <= 'Z')) // if operand then append it to postFix
{
{
postFix +=exp[i];
}
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') // if operator then check conditions
{
if(top != -1) // check for all the remaining values
{
if(Priority(exp[i])>Priority(Stack[top])) // if incoming is > then Push
{
Push(exp[i]);
}
else // if incoming is < then first Pop and then Push it to the Stack
{
while(Priority(exp[i]) <= Priority(Stack[top]))
{
postFix +=Pop();
}
Push(exp[i]);
}
}
else
{
Push(exp[i]);
}
}
}
while(top != -1) // pop the remaining elements
{
postFix +=Pop();
}
return postFix;
}
int Priority(char ch) // for checking priority
{
switch(ch)
{
case '(':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
}
}