-
Notifications
You must be signed in to change notification settings - Fork 19
/
Copy pathinfix_to_postfix.cpp
73 lines (61 loc) · 1.41 KB
/
infix_to_postfix.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
#include<bits/stdc++.h>
using namespace std;
//Function to return precedence of operators
int prec(char c) {
if(c == '^')
return 3;
else if(c == '/' || c=='*')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s) {
stack<char> st; //For stack operations, we are using C++ built in stack
string result;
for(int i = 0; i < s.length(); i++) {
char c = s[i];
// If the scanned character is
// an operand, add it to output string.
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;
// If the scanned character is an
// ‘(‘, push it to the stack.
else if(c == '(')
st.push('(');
// If the scanned character is an ‘)’,
// pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(c == ')') {
while(st.top() != '(')
{
result += st.top();
st.pop();
}
st.pop();
}
//If an operator is scanned
else {
while(!st.empty() && prec(s[i]) <= prec(st.top())) {
result += st.top();
st.pop();
}
st.push(c);
}
}
// Pop all the remaining elements from the stack
while(!st.empty()) {
result += st.top();
st.pop();
}
cout << result << endl;
}
//Driver program to test above functions
int main() {
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}