Implement the following infix-to-postfix algorithm in C++. Make sure you underst
ID: 3661825 • Letter: I
Question
Implement the following infix-to-postfix algorithm in C++. Make sure you understand the algorithm by going through a few examples with pencil and paper, only then start implementing it. Note the indentation implies the beginning and end of a block of code.
Determine the time complexity of the algorithm.
This algorithm can be modified by adding one more stack to evaluate expressions. Think about how you would do that. Hand in a printout of your program and a typescript of sample runs.
// An algorithm for infix to postfix expression conversion. //Forexample, a+b-c translatesto ab+c-
// a+b*c translatesto abc*+
// (a+2)/(5-d) goesto a2+5d-/
// a+((b-c)*d)/e to abc-d*e/+ // Valid operands are single digits and characters: 0-9 a-z A-Z // Valid operators are: + - * / ( )
else
print input
Explanation / Answer
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
// get precedence
// assigning higher number for greater prefrence
int prec(char ch) {
switch (ch) {
case '/': return 2;
case '*': return 2;
case '+': return 1;
case '-': return 1;
default : return 0;
}
}
// convert infix expression to postfix using a stack
void convertToPostfix(char infix[], char postfix[], int size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
while (i < size) {
ch = infix[i];
if (ch == '(') {
s.push(ch);
i++;
continue;
}
if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix[k++] = s.top();
s.pop();
}
if (!s.empty()) {
s.pop();
}
i++;
continue;
}
weight = prec(ch);
if (weight == 0) {
// we saw an operand
// simply append it to postfix expression
postfix[k++] = ch;
}
else {
if (s.empty()) {
s.push(ch);
}
else {
while (!s.empty() && s.top() != '(' &&
weight <= prec(s.top())) {
postfix[k++] = s.top();
s.pop();
}
s.push(ch);
}
}
i++;
}
while (!s.empty()) {
postfix[k++] = s.top();
s.pop();
}
postfix[k] = 0; // null terminate the postfix expression
}
// main
int main() {
char infix[] = "a+((b-c)*d)/e";
int size = strlen(infix);
char postfix[size];
convertToPostfix(infix,postfix,size);
cout<<" Infix Expression :: "<<infix;
cout<<" Postfix Expression :: "<<postfix;
cout<<endl;
return 0;
}