Implement a C++ program that converts an infix expression into a postfix express
ID: 663785 • Letter: I
Question
Implement a C++ program that converts an infix expression into a postfix expression and then evaluate the postfix expression. Use the List Class that has been provided below to handle these operations.
Print out the infix expression, the postfix expression and the calculated results of the expression.
You are to handle the (), + - * / and ^ (exponential/power) operators. The ^ operator precedence is higher than * and / operators.
To test your program, use the following input expressions. Put the input data into a file to be read in. Test your program with some simple expressions before using the data below and make sure each of your operations work correctly.
Input File.txt:
5 + 7
6 ^ 2 + 1
3 * 8 + 6
5 ^ 4 - 6 ^ 4
5 - 3 * 7 / 4 - 9
8 * ( 9 / 3 - 2 ) / 4 + 5 * 6
5 ^ 3 * 4 + ( 2 + ( 9 * 8 / ( 2 * 6 * ( 8 / 4 ) ) ) ^ 2 * 8 - 5 ) / 5 ^ 2 - 4
5 - 3 * 8 / 2 ^ 3
3 ^ 3 ^ 2 *3
8 * ( 6 / 3 - 2 ) / 4 + 5 * 6 +3
( ( ( ( ( 9 * 5 ) ) ) ) )
List Class:
class Entry
{
public:
int value;
int priority;
Entry()
{
value = 0;
priority = 0;
}
Entry(int aValue, int aPriority)
{
value = aValue;
priority = aPriority;
}
};
class List
{
private:
int CAPACITY;
Entry *arr;
int currentPos, size1;
public:
List()
{
CAPACITY = 20;
arr = (Entry *)malloc(CAPACITY * sizeof(Entry *));
size1 = 0;
currentPos = -1;
}
List(const List &obj)
{
CAPACITY = obj.CAPACITY;
size1 = obj.size1;
currentPos = obj.currentPos;
if(arr != NULL)
{
for(int i = 0; i < size1; i++)
arr[i] = obj.arr[i];
}
}
bool empty()
{
return size1 == 0;
}
void front()
{
if(size1 == 0)
cout << "List is empty!" << endl;
else
currentPos = 0;
}
void end()
{
if(size1 == 0)
cout << "List is empty!" << endl;
else
currentPos = size1 - 1;
}
void prev()
{
if(size1 <= 0)
cout << "Previous element is empty. ";
else
{
currentPos--;
}
}
void next()
{
if(currentPos >= CAPACITY - 1)
cout << "Next element is empty. ";
else
{
currentPos++;
}
}
int getPos()
{
return currentPos;
}
void setPos(int n)
{
if(n < 0 || n >= size1)
cout << "Position should not be out of range." << endl;
else
currentPos = n;
}
void insertBefore(Entry ele)
{
if(size1 == CAPACITY)
{
cout << "The list has reached max capacity. Cannot add more elements. ";
return;
}
else if(currentPos - 1 < 0)
{
cout << "No previous position. ";
return;
}
else
{
currentPos--;
arr[currentPos] = ele;
size1++;
}
}
void insertAfter(Entry ele)
{
if(size1 == CAPACITY)
{
cout << "The list is full. Elements have NOT been added. ";
return;
}
else if(currentPos + 1 >= CAPACITY)
{
cout << "No next position. ";
return;
}
else
{
currentPos++;
arr[currentPos] = ele;
size1++;
}
}
Entry getElement()
{
return arr[currentPos];
}
int size()
{
return size1;
}
void replace(Entry n)
{
if(currentPos < 0)
cout << "List is empty!" << endl;
else
arr[currentPos] = n;
}
void erase()
{
if(currentPos < 0)
cout << "List is empty!" << endl;
else
{
for(int i = currentPos; i < size1 - 1; i++)
{
arr[i] = arr[i + 1];
}
size1--;
}
}
void clear()
{
currentPos = -1;
size1 = 0;
arr = new Entry[CAPACITY];
}
void reverse()
{
for(int i = 0; i < size1 / 2; i++)
{
Entry tmp = arr[i];
arr[i] = arr[size1 - i];
arr[size1 - i] = tmp;
}
}
void swap(List a)
{
Entry *tmp = arr;
arr = a.arr;
a.arr = tmp;
}
friend ostream &operator<<(ostream &out, List &l)
{
for(int i = 0; i < l.size(); i++)
{
if(l.arr[i].value != 0)
out << l.arr[i].value << " - " << l.arr[i].priority << endl;
}
out << " ";
return out;
}
bool operator ==(List &l)
{
if(size1 != l.size1)
return false;
for(int i = 0; i < size1; i++)
{
if(arr[i].priority != l.arr[i].priority || arr[i].value != l.arr[i].value)
return false;
}
return true;
}
void operator=(List &l)
{
if(this != &l)
{
delete [] arr;
CAPACITY = l.CAPACITY;
size1 = l.size1;
arr = new Entry[CAPACITY];
currentPos = l.currentPos;
if(arr != NULL)
{
for(int i = 0; i < size1; i++)
arr[i] = l.arr[i];
}
}
}
};
class PriorityQueue
{
private:
List list;
public:
PriorityQueue()
{}
void enqueue(Entry ent)
{
list.insertAfter(ent);
}
Entry dequeue()
{
list.front();
Entry ent = list.getElement();
int index = 0;
for(int i = 1; i < list.size(); i++)
{
list.next();
if(list.getElement().priority > ent.priority)
{
ent = list.getElement();
index = i;
}
}
list.setPos(index);
list.erase();
return ent;
}
bool empty()
{
return list.empty();
}
};
Explanation / Answer
# include # include # include # include int top=-1; char Stack[100]={NULL}; void push(constchar); constchar pop( ); void infix_to_postfix(constchar *); int main( ) { clrscr( ); char Infix_expression[100]={NULL}; coutRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.