The program must accept an infix expression S and convert it to the corresponding postfix expression.
Boundary Condition(s):
3 <= Length of S <= 100
Example Input/Output 1:
Input:
A*B*(C+D)%R+F-G/H*J
Output:
AB*CD+*R%F+GH/J*-
Example Input/Output 2:
Input:
a+b*(c^d-e)^(f+g*h)-i
Output:
abcd^e-fgh*+^*+i-
#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isOperand(char c) {
return (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z');
}
bool isOperator(char c) {
if (c == '(')
return true;
if (c == '%')
return true;
if (c == ')')
return true;
if (c == '+')
return true;
if (c == '-')
return true;
if (c == '*')
return true;
if (c == '/')
return true;
if (c == '^')
return true;
return false;
}
int prec(char c) {
if (c == '+')
return 3;
if (c == '%')
return 4;
if (c == '-')
return 3;
if (c == '*')
return 4;
if (c == '/')
return 4;
if (c == '^')
return 5;
return -1;
}
string ItoP(string s) {
int i, l = s.length();
string postfix = "";
stack < char > stack;
for (i = 0; i < l; i++) {
if (isOperand(s[i])) {
postfix = postfix + s[i];
}
if (isOperator(s[i])) {
if (stack.empty()) {
stack.push(s[i]);
} else {
if (s[i] == '(') {
stack.push(s[i]);
} else {
if (s[i] == ')') {
while (stack.top() != '(') {
postfix = postfix + stack.top();
stack.pop();
}
stack.pop();
} else if (prec(s[i]) > prec(stack.top()) || s[i] == '^') {
stack.push(s[i]);
} else {
while (!stack.empty() && stack.top() != '(' && prec(stack.top()) >= prec(s[i])) {
postfix = postfix + stack.top();
stack.pop();
}
stack.push(s[i]);
}
}
}
}
}
while (!stack.empty()) {
postfix = postfix + stack.top();
stack.pop();
}
return postfix;
}
int main() {
string s;
cin >> s;
cout << ItoP(s) << endl;
}
Leave a Reply