Infix to Toatfi Write a Cee program that ill aocept infix expressions (1ike 5.(4
ID: 3890127 • Letter: I
Question
Infix to Toatfi Write a Cee program that ill aocept infix expressions (1ike 5.(4 8)) and eonvert them to post tix. You re tus. DLJkatra's algoritha for eoaverting. ijkstra's Algorithm Read in lin into a serina Print the atring while there aze eharacters left to process in the sering get a token takip over blanks) if th token is a digit then output(token if the tokenis then pash(token) f the token is then while the top iten ia not and output(t popitemp it the stack eapty then push. taken set enpty and the prlorlty (token)-prlority (top item on the stack hile the stack is not enpty do pop(tenp) and outputtep where inpat for the aaaignment 23-5 25 (23) 2 Outpat for the aaaignnent 1s 23-5 35 21 2 3 5- 2356 a 23-5-2- 4 235-6 S: 235-4 63 (232 23 5-4 4-2+1- 2356-+4- 2354- 3 62 You might also ery 23 4-2/ 3-45 2/3/9 PEOgENing Notes You are to write a well-c osed program. The atack routines are to be defined as nethods in a elass and aro t b, in a serparat filExplanation / Answer
Below is your program :-
#include <iostream>
#include <string>
using namespace std;
bool isChar(char a) {
a = int(a);
if (((a>=65)&&(a<=90))||((a>=97)&&(a<=122)))
return true;
else return false;
}
bool isOperator(char a) {
switch (a) {
case '+': return true;
case '-': return true;
case '*': return true;
case '/': return true;
case '(': return true;
case ')': return true;
case '^': return true;
default: return false;
}
}
int order(char op) {
switch (op){
case '+': return 1;
case '-': return 1;
case '*': return 2;
case '/': return 2;
case '^': return 3;
default: return 0;
}
}
bool isHigher(char a, char b) {
if(order(a)>=order(b)) return true;
else return false;
}
string pop(string s) {
return s.substr(0,s.size()-1);
}
string toPostfix(string infix) {
string postfix, stack;
for(int i=0; i<infix.length(); ++i) {
//if operand
if(isChar(infix[i])) {
postfix.push_back(infix[i]);
}
//if operator
else if(isOperator(infix[i])) {
//if stack is empty
if(stack.empty()) {
stack.push_back(infix[i]);
}
//if stack not empty
else if(!stack.empty()) {
//if (
if(infix[i]=='(') {
stack.push_back(infix[i]);
}
//if ) is encountered pop till ( to postfix
else if(infix[i]==')') {
while(*(stack.end()-1)!='(') {
postfix.push_back(*(stack.end()-1));
stack = pop(stack);
}
stack=pop(stack);
}
else {
//pop until tos has lesser precedence or tos is null.
while(isHigher(*(stack.end()-1),infix[i])) {
postfix.push_back(*(stack.end()-1));
stack = pop(stack);
}
if(!(isHigher(*(stack.end()-1),infix[i])))
stack.push_back(infix[i]);
}
}
}
}
while(!stack.empty()) {
string::iterator tos = stack.end() - 1;
postfix.push_back(*tos);
stack = pop(stack);
}
return postfix;
}
int main() {
int t;
cin>>t;
string infix[t], postfix[t];
for(int i = 0; i < t; ++i) {
cin>>infix[i];
}
for(int i = 0; i < t; ++i) {
postfix[i] = toPostfix(infix[i]);
cout<<" "<<postfix[i];
}
return 0;
}