A stack is a special type of list with restricted access operations. Typically,

Question

A stack is a special type of list with restricted access operations. Typically, a stack is viewed as a vertical list in which items can only be added (pushed), removed (pop) or viewed (peek) from the list at the top. A typical stack class will offer a limited set of methods something like the following:
class stack
{
public:
stack();
~stack();
bool isEmpty() const;
int top() const; // Return the int at the top of the stack
void push(int x); // Push a new int on the stack
void pop(); // Remove the item at the top of the stack
};

Because a stack is essentially a simplified list, we can implement a stack in much the same way that we implemented a list in assignment 1. Because the stack is actually simpler than the list in its behavior, we can make the implementation of the stack even simpler than the implementation of the list in assignment 1.
Here is an outline of how we could implement a stack class. The stack is implemented as a dynamic array. The stack class itself just contains one pointer, a pointer to the item at the top of the stack.
Implement the stack class following this outline

Stack class application - evaluating arithmetic statements
As a second part of this programming exercise, we will also write a program that implements the stack. The problem is to evaluate arithmetic expressions written in postfix form. In postfix form, the operands of an arithmetic statement appear followed by the operator. Here are some examples of arithmetic expressions written in postfix form:
1 2 + // Equivalent to 1+2
2 3 4 + * // Equivalent to (2 * (3 + 4))
2 3 + 4 * // Equivalent to (2 + 3)*4

Stack class application - Infix to Postfix Conversion
The last ingredient we need in order to be able to evaluate arbitrary arithmetic expressions is an algorithm to translate infix expression to postfix expressions.
Here is the beginning of an outline of that algorithm. The algorithm uses a queue to store the results and a stack to store operators while the algorithm runs. Each operator has a precedence associated with it, as shown in the table.
Here is the outline of the algorithm.

Scan the expression from left to right. If you encounter a number token, move it immediately to the result queue. If you encounter an operator and the operator stack is empty, push the operator on the stack. If you encounter an operator whose precedence is greater than that of the operator at the top of the stack, push the new operator on the stack. If you encounter an operator whose precedence is less than or equal to the precedence of the operator at the top of the stack, pop the stack and move the operator from the stack to the output queue. Repeat this step until either the stack empties or an operator appears at the top of the stack whose precedence is smaller than the precedence of the current operator. Push the new operator on the stack. When you reach the end of the input, move any remaining operators from the stack to the result queue.

Assignment Task:
Your assignment is to write a C++ program that uses stack class and the algorithms outlined above and do the following tasks
1. Take infix expression from user and convert it to postfix expression after verifying that user has entered correct expression.
2. Evaluate postfix arithmetic expression (taken from user in infix form and converted to postfix). Your program should support the use of both positive and negative integers, and all five of the integer arithmetic operators, +, - , *, /, and %.
Here is a helpful hint. One problem you will have to solve is how to scan the input the user types and separate it into integers and operators. Something you will find useful to help you do this is the cin.peek() method.peek() returns a C++ char telling you what the next character in the input stream is without actually removing that character from the input stream. Another useful method is get(), which returns the next character in the input stream.
Here is some code to demonstrate how you can use peek() and get() to read the input line and do the right thing with the input.
do {
char ch = cin.peek();
if(ch >= '0' && ch <= '9')
{
// Read an integer
int n;
cin >> n;
// Insert code here to do the right thing with n
}
else if(ch == ' ')
ch = cin.get(); // skip the space
else
{
ch = cin.get();
// ch is an operator or the - at the start of a number
// Insert code here to do the right thing.
}
} while(cin.peek() != ' ');
The loop contains a test to make it stop correctly at the end of the input line

your code must be in c++ language

Explanation / Answer

// 1. Infix to postfix #include #include #include const int MAX = 50 ; class infix { private : char target[MAX], stack[MAX] ; char *s, *t ; int top ; public : infix( ) ; void setexpr ( char *str ) ; void push ( char c ) ; char pop( ) ; void convert( ) ; int priority ( char c ) ; void show( ) ; } ; infix :: infix( ) { top = -1 ; strcpy ( target, "" ) ; strcpy ( stack, "" ) ; t = target ; s = "" ; } void infix :: setexpr ( char *str ) { s = str ; } void infix :: push ( char c ) { if ( top == MAX ) cout

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.