DS_A2

Data Structures
CC113
Assignment # 02
Name: Hammad Ali

Program: BS CS Semester III
Enrollment Number: 23018020050
Submitted to: Dr. Sameer Malik
KNOWLEDGE UNIT OF SYSTEMS AND

TECHNOLOGY, UMT, SIALKOT
Program Objective
Create a converter for:
• Infix to Postfix Conversion

• Infix to Prefix Conversion
Implementation
Stack.cpp (Building Block)
#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;
template <class T>

class Stack
{
private:
T *stack;
int capacity;
int top;
void resize()
{
capacity *= 2;
T *newStack = new T[capacity];
for (int i = 0; i <= top; i++)
{
newStack[i] = stack[i];
}
delete[] stack;
stack = newStack;
}
bool isFull()
{
return top == capacity - 1;
}
public:
Stack(int _capacity = 5) : capacity(_capacity), top(-1)
{
stack = new T[capacity];
}
void push(T val)
{
if (isFull())
resize();
stack[++top] = val;
}
T pop()
{
T val;
try
{
if (isEmpty())
throw runtime_error("Can't pop from empty stack!\n");
val = stack[top--];
}
catch (exception &ex)
{
cout << ex.what();
}
return val;
}
T peek()
{
T val;
try
{
if (isEmpty())
throw runtime_error("Can't access top of empty stack!\n");
val = stack[top];
}
{
cout << ex.what();
}
return val;
}
T* getStack()
{
return stack;
}
bool isEmpty()
{
return top == -1;
}
int getSize()
{
return top + 1;
}
~Stack()
{
delete[] stack;
}
};
Converter.cpp (Conversion Logic)
#include <iostream>
#include "Stack.cpp"
#include "Table.cpp"
class Converter
{
private:
bool isOperator(char &c)
{
return (
c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^' || c == '(' ||
c == ')');
}
int getPrecedence(char c)
{
switch (c)
{
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
default:
return 0;
}
}
void reverseExpression(string& expression)
{
int n = expression.length();
for (int i = 0; i < n/2; i++)
{
swap(expression[i], expression[n-i-1]);
swapParanthesis(expression[i]);
swapParanthesis(expression[n-i-1]);
}
}
void swapParanthesis(char& c)
{
if (c == '(')
c = ')';
else if (c == ')')
c = '(';
}
bool checkParanthesis(string &expression)
{
Stack<char> braces;
for (char& c : expression)

{
if (c == '(')
braces.push(c);
else if (c == ')')
braces.pop();
}
return braces.isEmpty();
}
public:
string toPostfix(string expression)
{
if (!checkParanthesis(expression))
return "The expression entered is not valid!\n";
string output;
Stack<char> operators;
Table table(expression.length());
table.displayHeader();
for (char &c : expression)

{
if (isOperator(c))
{
if (c == '(' || operators.isEmpty())
{
operators.push(c);
}
else if (c == ')')
{
while (operators.peek() != '(')
{
output += operators.peek();
operators.pop();
}
operators.pop();
}
else
{
while (!operators.isEmpty()
&& operators.peek() != '('
&& getPrecedence(c) <=
getPrecedence(operators.peek())
)
{
operators.pop();
}
operators.push(c);
}
}
else
{
output += c;
}
table.displayRow(c, operators.getStack(), operators.getSize(),

output);
}
while (!operators.isEmpty())
{
operators.pop();
}
table.displayLineBreak();
return output;
}
string toPrefix(string expression, bool displayTable = true)
{
if (!checkParanthesis(expression))
return "Invalid Expression\n";
reverseExpression(expression);
expression = toPostfix(expression);
reverseExpression(expression);
return expression;
}
};
Table.cpp (Formatting Class)

#include <iostream>
#include <string>
class Table
{
private:
int maxColumnWidth;
public:
Table(int _maxColumnWidth) : maxColumnWidth(max(_maxColumnWidth, 30))
{}
void displayHeader()
{
displayLineBreak();
cout << "| Symbol | Stack";

for (int i = 6; i < maxColumnWidth; i++)
cout << ' ';
cout << "| Expression |\n";
displayLineBreak();
}
void displayLineBreak()
{
for (int i = 0; i < maxColumnWidth + 24; i++)
cout << '-';
cout << '\n';
}
void displayRow(char& symbol, char* stack, int stackSize, string&
output)
{
cout << " " << symbol << " | ";
for (int i = 0; i < stackSize; i++)

cout << stack[i];
for (int i = stackSize; i < maxColumnWidth - 1; i++)

cout << ' ';
cout << "| " << output << '\n';

}
};
Main.cpp (Program Interface)

#include <iostream>
#include <stdexcept>
#include <limits>
#include "Converter.cpp"
void pause()
{
cout << "\nPress enter to continue...";
cin.get();
system("clear");
}
int main()
{
Converter converter;
string expression, postfix, prefix;
cin.exceptions(ios::failbit | ios::badbit);
while (true)
{
cout << "-------------------------------\n";
cout << "| Notation Converter |\n";
cout << "-------------------------------\n";
cout << "| 1. Convert Infix to Postfix |\n";
cout << "| 2. Convert Infix to Prefix |\n";
cout << "| 3. Exit Program |\n";
cout << "-------------------------------\n";
cout << "\nEnter choice: ";
int choice;
try
{
cin >> choice;
cout << '\n';
}
{
cout << "Invalid Input. Please try again\n";
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
pause();
continue;
}
switch (choice)
{
case 1:
cout << "Enter expression: ";
cin >> expression;
postfix = converter.toPostfix(expression);
cout << "Expression in postfix: " << postfix << '\n';
break;
case 2:
cout << "Enter expression: ";
cin >> expression;
prefix = converter.toPrefix(expression);
cout << "Expression in prefix: " << prefix << '\n';
break;
case 3:
cout << "Thank you for using our program!\n\n";
return 0;
default:
cout << "Invalid Choice! Please retry\n";
}
cin.ignore();
pause();
cout << '\n';

}
}
Output
Infix to Postfix Infix to Prefix
THE END

DS_A2

Uploaded by

Copyright:

Available Formats

DS_A2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS_A2

Uploaded by

Copyright:

Available Formats

Data Structures

Name: Hammad Ali

Submitted to: Dr. Sameer Malik

KNOWLEDGE UNIT OF SYSTEMS AND

• Infix to Postfix Conversion

template <class T>

for (char& c : expression)

for (char &c : expression)

table.displayRow(c, operators.getStack(), operators.getSize(),

Table.cpp (Formatting Class)

cout << "| Symbol | Stack";

for (int i = 0; i < stackSize; i++)

for (int i = stackSize; i < maxColumnWidth - 1; i++)

cout << "| " << output << '\n';

Main.cpp (Program Interface)

cout << '\n';

Infix to Postfix Infix to Prefix

You might also like