In this assignment you will write a program called \" infix.cpp \", that uses a
ID: 3674820 • Letter: I
Question
In this assignment you will write a program called "infix.cpp", that uses a stack,implemented as a singly-linked list, to convert a postfix expression to the corresponding fully-parenthesized infix expression. Consider the following examples:
1. the postfix expression a b + c d - * will be converted to the infix ((a + b) * (c - d))
2. the the postfix expression a b + will be converted to the infix (a + b)
3. the postfix expression a b / c d / / will be converted to infix ((a / b) / (c / d))
4. for the postfix expression a b / c * + the program should print the error message "too many operators and not enough operands".
5. for the postfix expression a b c d / + e * f the program should print the error message "too many operands and not enough operators".
6. for postfix expression a will be converted to the infix (a)
7. for an empty (string) expression an empty (string) expression will be returned
8. for postfix + the program should print the error message “too many operators not enough operands”
Notes: 1. Include one space between operands ( eg. a b c d ) and operator (eg. + - * /) in your
input to the program.
2. The only operators to consider are +, -, * and /.
Your program should ask the user for a postfix expression as input, and it should output the corresponding fully-parenthesized infix expression. The program should also ask the user if he/she would like to do another conversion. If so, the user should be able to enter another posfix expression; otherwise the program should terminate. Also, the stack must be implemented using a singly-linked list. Your driver, infix.cpp, should include the definition and declaration files for the class STACK, stack.cpp and stack.h, respectively, meaning that the standard class stack shouldn't be used but instead declaring a new class.
Your program should do error-checking. For example, if the infix expression is invalid, your program should print an error message stating so.
Explanation / Answer
File Name: Satck1.cpp
/**Stack Implementation as a Singly- Linked List**/
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *next;
int data;
};
class stack : public node
{
node *head;
int tos;
public:
stack()
{
tos=-1;
}
void push(int x)
{
if (tos < 0 )
{
head =new node;
head->next=NULL;
head->data=x;
tos ++;
}
else
{
node *temp,*temp1;
temp=head;
if(tos >= 4)
{
cout <<"stack over flow";
return;
}
tos++;
while(temp->next != NULL)
temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
}
}
void display()
{
node *temp;
temp=head;
if (tos < 0)
{
cout <<" stack under flow";
return;
}
while(temp != NULL)
{
cout <<temp->data<< " ";
temp=temp->next;
}
}
void pop()
{
node *temp;
temp=head;
if( tos < 0 )
{
cout <<"stack under flow";
return;
}
tos--;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
temp->next=NULL;
}
};
main()
{
stack s1;
int ch;
while(1)
{
cout <<" 1.PUSH 2.POP 3.DISPLAY 4.EXIT enter ur choice:";
cin >> ch;
switch(ch)
{
case 1: cout <<" enter a element";
cin >> ch;
s1.push(ch);
break;
case 2: s1.pop();break;
case 3: s1.display();
break;
case 4: exit(0);
}
}
return (0);
}
File Name: Infix1.cpp
/** convert a postfix expression to the corresponding fully-parenthesized infix expression **/
#include "stack1.cpp”
#include <string>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <cctype>
int getValidChoice ();
void readString(string& s);
void printString(const string& s);
void convertPostfix(string& post, string& result);
void convert(StackType & s, char ch);
void evalPostfix(string& post, double& answer);
void evaluate(StackType & s, char ch);
void error(int m);
void main()
{
string post;
double answer;
int choice;
choice = getValidChoice();
while (choice != 3) {
//switch menu options
switch (choice)
{
case 1:
cout<<"Please enter a postfix expression: ";
readString(post);
if (post == "") //error if string empty
error(1);
else
{
evalPostfix(post, answer);
printString(post);
cout<<" = "<<answer<< endl << endl;
}
break;
case 2:
cout<<"Please enter a postfix expression: ";
readString(post);
if (post == "")
error(1);
else
{ string tempString = "";
convertPostfix(post, tempString);
cout<<"Postfix expression: ";
printString(post);
cout<<" Epression converted to infix: ("<<tempString << ")"<<endl<<endl;
}
break;
default: //if choice is not recognized print error
error(3);
} //end switch
choice = getValidChoice();
} //end while
}
int getValidChoice ()
{
int choice;
//display menu options
cout<<" Options ";
cout<< " (1) Evaluate postfix expression " << endl;
cout<< " (2) Convert postfix to infix " << endl;
cout<< " (3) Quit " << endl;
//get menu option
cout<<"Enter option: ";
cin>>choice;
cout <<endl;
//validate menu option
while ((choice < 1) || (choice > 3)) {
cout << "Enter a value between 1 and 3: ";
cin >> choice;
}
return choice;
}
void printString(const string& s)
{
if (s.empty())
cout<<"Empty"; //if string is empty print "empty"
else
cout<<s;
}
void readString(string& s)
{
char temp[40];
cin.ignore(80,' '); //clear buffer
cin.getline(temp, 40); //copy line to string
s = temp;
}
void evalPostfix(string& post, double& answer)
{
int index = 0, total = 0;
double tempDbl;
bool negative = false; //to detect negative signs
StackType s; //declare a stack of doubles
//loop index until end of string
while (index < (int) post.length())
{
//pass over spaces in string
while (isspace(post[index]))
index++ ;
//if operator evaluate incrementing index
if (!isdigit(post[index]) &&
!((index+1 < (int) post.length()) &&
(post[index] == '-' && isdigit(post[index+1]))))
//if (!isdigit(post[index]))
evaluate(s, post[index++]);
else
{ //if number, checks for negative sign
if (post[index] == '-')
{
index++;
negative = true;
}
//add up the digits from string
while ((post[index] >= '0') && (post[index] <= '9'))
total = (total * 10) + (post[index++] - '0');
//if there was a negative sign, negate total
if (negative)
{
total = total * -1;
negative = false;
}
//push number onto stack
s.push(total);
total = 0;
}
index++;
}
//pop answer from stack
s.pop(tempDbl);
answer = tempDbl;
}
void evaluate(StackType & s, char ch)
{
double op1, op2;
//check if empty before popping operands
if (!s.isEmpty())
{
s.pop(op2);
if (!s.isEmpty())
{
s.pop(op1);
//push result
switch(ch)
{
case '+':
s.push(op1 + op2);
break;
case '-':
s.push(op1 - op2);
break;
case '*':
s.push(op1 * op2);
break;
case '/':
s.push(op1 / op2);
break;
default:
return;
}
}
}
}
void convertPostfix(string& post, string& result)
{
int index = 0;
string tempString;
StackType s; //declare a stack of strings
//loop index until end of string
while (index < (int) post.length())
{
//pass over spaces in string
if (isspace(post[index]))
index++ ;
//if operator convert incrementing index
if (!isdigit(post[index]) &&
!((index+1 < (int) post.length()) &&
(post[index] == '-' && isdigit(post[index+1]))))
//if (!isdigit(post[index]))
convert(s, post[index++]);
else
{
//clear string
tempString.erase();
//concatenate numbers to string
while (!isspace(post[index]))
tempString = tempString + post[index++];
//push string onto stack
s.push(tempString);
}
index++;
}
//pop resulting string from stack
s.pop(result);
}
void convert(StackType & s, char ch)
{
string op1, op2, tempString;
//check if empty before popping
if (!s.isEmpty())
{
s.pop(op2);
if (!s.isEmpty())
{
s.pop(op1);
//constructing string for result
tempString = tempString + "( ";
tempString = tempString + op1;
//concatenate sign to string
switch(ch)
{
case '+':
tempString = tempString + " + ";
break;
case '-':
tempString = tempString + " - ";
break;
case '*':
tempString = tempString + " * ";
break;
case '/':
tempString = tempString + " / ";
break;
default:
return;
}
//adding rest of the string
tempString = tempString + op2;
tempString = tempString + " )";
//push resulting string onto stack
s.push(tempString);
}
}
}
void error(int m)
{
system("cls"); //clear screen
cout<<""; //system beep
//displays error message according to parameter passed
switch (m)
{
case -1:
cout<<"too many operators and not enough operands";
break;
case 1:
cout<<"ERROR - Postfix expression empty.";
break;
case 3:
cout<<" too many operands and not enough operators ";
break;
default:
cout <<"UNKNOWN ERROR.";
}
cout << endl << endl;
}
void intro()
{
system("cls"); //clear screen
//displays welcome message
cout<<"Postfix Calculator and Converter ";
}