Statement of Work: Implement a generic stack container. Implement a program that
ID: 3884636 • Letter: S
Question
Statement of Work: Implement a generic stack container. Implement a program that converts infix expression to postfix expression and implement a program that evaluates postfix expression using the stack container you developed.
Project Description:
A stack is a type of data container/data structure that implements the LAST-IN-FIRST-OUT (LIFO) strategy for inserting and recovering data. This is a very useful strategy, related to many types of natural programming tasks.
Remember that in the generic programming paradigm, every data structure is supposed to provide encapsulation of the data collection, enabling the programmer to interact with the entire data structure in a meaningful way as a container of data. By freeing the programmer from having to know its implementation details and only exporting the interface of its efficient operations, a generic Stack provides separation of data access/manipulation from internal data representation. Programs that access the generic Stack only through the interface can be re- used with any other Stack implementation, which results in modular programs with clear functionality and that are more manageable
Goals: 1. Implement a generic Stack.
2. Write a program that parses Infix arithmetic expressions to Postfix arithmetic expressions using a Stack.
3. Write a program that evaluates Postfix arithmetic expressions using a Stack.
Task 1: Implement a GenericStack:
GenericStack: MUST store elements internally in a BasicContainer. It should use only the public interface to BasicContainer, as you will compile/link your GenericStack implementation with the BasicContainer class. Therefore, in particular:
• GenericStack MUST:
o be able to store elements of an arbitrary type.
o have a no-argument constructor that initializes it to some size. This size MUST NOT be so large as to prevent a calling program to initialize several GenericStack instances in a single execution. Suggested length values are 10, 16, or 256.
• Every GenericStack instance holding n elements MUST accept insertions as long as the system has enough free memory to dynamically allocate an array of 2n+1 elements at insertion request time, regardless of the initial capacity of the GenericStack. If the system does not have such free memory, GenericStack MUST report an error message as the result of the insertion request.
• GenericStack MUST implement the full interface specified below.
• You MUST provide both the template (in a class named GenericStack.h) and the implementation (in a class named GenericStack.cpp).
Interface:
The interface of GenericStack is specified below. It provides the following public functionality, all of which can be efficiently achieved using an internal array representation for the data.
GenericStack():no-argument constructor. Initializes the Stack to some pre-specified capacity.
~GenericStack (): destructor.
GenericStack (const GenericStack &): copy constructor.
GenericStack& operator= (const GenericStack &): assignment operator.
bool empty() const: returns true if the GenericStack contains no elements, and false otherwise.
void push(const T& x): adds x to this GenericStack.
void pop(): removes and discards the most recently added element of the GenericStack.
T& top(): mutator that returns a reference to the most recently added element of the GenericStack.
const T& top() const: accessor that returns the most recently added element of the GenericStack.
int size(): returns the number of elements stored in this GenericStack.
void print(std::ostream& os, char ofc = '') const: print this instance of GenericStack to ostream os. Note that gs.print() prints elements in opposite order as if bc.print() was invoked in the underlying BasicContainer.
The following non-member functions should also be supported:
std::ostream& operator<< (std::ostream& os,const GenericStack& a): invokes the print() method to print the GenericStack a in the specified ostream.
bool operator== (const GenericStack&,const GenericStack &): returns true if the two compared "GenericStack"s have the same elements, in the same order.
bool operator< (const GenericStack& a, const GenericStack & b): returns true if every element in GenericStack a is smaller than corresponding elements of GenericStatck b, i.e., if repeatedly invoking top() and pop() on both a and b will generate a sequence of elements a_i from a and b_i from b, and for every i, a_i < b_i, until a is empty.
Task 2: Convert Infix Arithmetic Expressions into PostFix Arithmetic Expressions and evaluate them (whenever possible)
For the sake of this exercise, an arithmetic expression is a sequence of space-separated strings. Each string can represent an operand, an operator, or parentheses.
Examples of operands: "34", "5", "a", and "b1" (alphanumeric)
Operators: one of the characters "+", "-", "*", or "/". As usual, "/" and "*" are regarded as having higher precedence than "+" or "-"
Parentheses: "(" or ")"
An Infix arithmetic expression is the most common form of arithmetic expression used.
Examples: (5 + 3) * 12 - 7 is an infix arithmetic expression that evaluates to 89
5 + 3 * 12 – 7 is an infix arithmetic expression that evaluates to 34
For the sake of comparison, postfix arithmetic expressions (also known as reverse Polish notation) equivalent to the above examples are:
5 3 + 12 * 7 –
5 3 12 * + 7 –
Two characteristics of the Postfix notation are (1) any operator, such as "+" or "/" is applied to the two prior operand values, and (2) it does not require ever the use of parentheses.
More examples:
a + b1 * c + ( dd * e + f ) * G in Infix notation
becomes a b1 c * + dd e * f + G * + in Postfix notation.
To implement Infix to Postfix conversion with a stack, one parses the expression as sequence of space-separated strings. When an operand (i.e., an alphanumeric string) is read in the input, it is immediately output. Operators (i.e., "-", "*") may have to be saved by placement in the operator_stack.We also stack left parentheses. Start with an initially empty operator_stack.
Follow these 4 rules for processing operators/parentheses:
1. If input symbol is "(", push it into stack.
2. If input operator is "+", "-", "*", or "/", repeatedly print the top of the stack to the output and pop the stack until the stack is either (i) empty; (ii) a "(" is at the top of the stack; or (iii) a lower-precedence operator is at the top of the stack. Then push the input operator into the stack.
3. If input operator is ")" and the last input processed was an operator, report an error. Otherwise, repeatedly print the top of the stack to the output and pop the stack until a "(" is at the top of the stack. Then pop the stack discarding the parenthesis. If the stack is emptied without a "(" being found, report error.
4. If end of input is reached and the last input processed was an operator or "(" report error. Otherwise print the top of the stack to the output and pop the stack until the stack is empty. If an "(" is found in the stack during this process, report error.
Evaluating Postfix Arithmetic Expressions
After converting a given expression in Infix notation to Postfix notation, you will evaluate the resulting arithmetic expression IF all the operands are numeric (int, float, etc.) values. Otherwise, if the resulting Postfix expression contains characters, your output should be equal to the input.
Example inputs:
5 3 + 12 * 7 –
5 3 12 * + 7 –
3 5 * c – 10 / Example outputs: 89
34 3 5 * c – 10 /
To achieve this, you will have an operand_stack, initially empty. Assume that the expression contains only numeric operands (no variable names). Operands are pushed into the stack as they are ready from the input. When an operator is read from the input, remove the two values on the top of the stack, apply the operator to them, and push the result onto the stack. If an operator is read and the stack has fewer than two elements in it, report an error. If end of input is reached and the stack has more than one operand left in it, report an error. If end of input is reached and the stack has exactly one operand in it, print that as the final result, or 0 if the stack is empty.
Summarizing Task 2 Your program should expect as input from (possibly re-directed) stdin a series of space- separated strings. If you read a1 (no space) this is the name of the variable a1 and not "a" followed by "1". Similarly, if you read "bb 12", this is a variable "bb" followed by the number "12" and not "b" ,"b", "12" or "bb", "1" ,"2".
Your program should convert all Infix expressions to Postfix expressions, including expressions that contain variable names. The resulting Postfix expression should be printed to stdout.
Your program should evaluate the computed Postfix expressions that contain only numeric operands, using the above algorithm, and print the results to stdout.
Restrictions:
1. You MAY NOT use any C++ STL classes in addition to the GenericStack, BasicContainer, and ANSI string class for all your data structures.
2. The Infix to Postfix conversion MUST be able to convert expressions containing both numbers and variable names (alphanumeric strings). Variable names may be arbitrary strings, such as "sci_fi_freak88".
3. You MAY use the "ctype.h" (alpha/digit check) and "stdlib.h" (alpha to digit/float conversion) library.
4. Their program MUST be able to produce floating number evaluation (i.e., deal with floats correctly).
5. Your program MUST NOT attempt to evaluate postfix expressions containing variable names. It should print the Postfix-converted result to stdout and MAY NOT throw an exception nor reach a runtime error in that case.
6. You MUST check for mismatched parentheses.
7. Their program MUST re-prompt the user for the next infix expression. Your program must be able to process several inputs at a time.
Deliverable Requirements:
Your implementation should be contained in three files, which MUST be named GenericStack.h, GenericStack.cpp and in2post.cpp. Note that we will use our own implementation of BasicContainer.cpp to test your code. So make sure that all calls made by your GenericStack class to your BasicContainer class use the public interface of BasicContainer. Submit your implementation in a tar file including the three files (GenericStack.h, GenericStack.cpp, and in2post.cpp) and the makefile you used.
Explanation / Answer
in2post.cpp
---------------------------
#include<iostream>
#include<string>
#include<cctype>
#include "stack.h"
using namespace std; // std::
using namespace cop4530; // include the self-implemented Stack container
int priority( char a ); // define the priority of arithmetic signs, the smaller the higher priority
bool IsOperator( char a ); // decide if a char is operator or otherwise
void skip_space(); // skip any while space in istream, focus on only operand and operator
void read_operand( Stack<string>& st, bool& flg, bool& flg1);
// read the next operand entirely, and decide if the
// operand is a integer, double, or variable
char IsTokenOperator( string& a ); // if a string element of a Stack container is operator, return it
int main() {
Stack<char> c_operator;
// stores the operator immediately onto the virtual output
Stack<string> postfix;
// stores the postfix expression in this Stack
// error messages, warning provided if anything happens
const string error1 = "Error: Missing operand in postfix string. Unable to evaluate postfix string! ";
const string error2 = "Error: Missing operator in postfix string. Unable to evaluate postfix string! ";
const string error3 = "Error: Mismatch parenthesis. Uable to evaluate postfix string! ";
while( !cin.eof() ) {
c_operator.clear(); // clean the container before operation
postfix.clear(); // ~~
int opera_balance = 0; // the number of operator, finally, should always be less than that of operand by 1
int paren_balance = 0; // the number of '(' should be equal than that of ')'
cout << "Enter infix expression (" << '"' << "exit" << '"' << "to quit): ";
bool flag = true; // decide whether expression has a variale rather than purely numerical values
bool isDouble = false; // by default, the operand is not a double type
while( ( !cin.eof() )&&( cin.peek() != ' ' ) ) { // read and push result to Stack until end of file
skip_space();
char next; // the next char awaits in istream
next = cin.peek(); // peek the next char in istream cin
if( isalpha( next ) || isdigit( next ) || ( next == '.' ) ) {
// in case of reading a var or num, then we unconditionally push it to postfix immediately
if( isalpha( next ) || ( next == '_' ) )
flag = false; // even one of the elements in string does not belong to digit or floating point, it is not a number
if( next == '.' )
isDouble = true; // when floating point appears, the operand is a double
read_operand( postfix, flag, isDouble ); // read in the whole operand, change flag if necessary
opera_balance++; // number of operand adds 1
} // end of 'if'
else if( IsOperator( next ) ) { // in case of reading an operator, namely, + - * or /, from istream
char operation;
cin.get( operation ); // put this char in istream and store it
opera_balance--; // the difference between operand and operator decreases by 1
if( c_operator.empty() ) {
// if the current operator stack is empty
c_operator.push( operation );
}
else if( ( !c_operator.empty() ) && ( priority( operation ) < priority( c_operator.top() ) ) ) {
// if the operator stack is not empty and the next operator has higher priority than the one on top
skip_space();
read_operand( postfix, flag, isDouble ); // read the next operand in, before push this operator to postfix stack
opera_balance++;
string temp;
temp.clear();
temp = temp + operation; // this is to convert the operator char to string for storage
postfix.push( temp );
}
else if( ( !c_operator.empty() ) && ( priority( operation ) >= priority( c_operator.top() ) ) && ( priority( c_operator.top() ) > 1 ) ) {
// if the operator stack is not empty and the next operator has equal or lower priority than the one one top
string temp;
temp.clear();
// then push the operator on top to postfix stack, and pop it out from c_operator stack before push the new operator in it
temp = temp + c_operator.top();
postfix.push( temp );
c_operator.pop();
c_operator.push( operation );
}
else if( ( !c_operator.empty() ) && ( priority( c_operator.top() ) == 0 ) )
// if the operator stack is not empty and the top() is exactly '('
c_operator.push( operation );
else { // unexpected manner, undefined
cout << " Unexpected arithmetic... ";
break; // jump out of loops, stop the program
}
} // end of 1st else if
else if( next == '(' ) { // if a '(' appears, just push it in c_operator
char Paren;
cin.get( Paren );
c_operator.push( Paren );
paren_balance++; // a single '(' breaks the parenthesis balance
} // end of 2nd else if
else if( next == ')' ) { // if parenthesis is enclosed finally;
char Paren;
cin.get( Paren );
paren_balance--;
while( c_operator.top() != '(' ) {
// pop out whatever left between '(' and ')' after push the leftovers to postfix stack
string temp;
temp.clear(); // clean the temp string;
temp = temp + c_operator.top();
c_operator.pop();
postfix.push( temp );
}
c_operator.pop(); // pop out the '('
} // end of 3rd else if
else { // user input "exit" to quit
cout << "Program stops. Existing program... ";
break;
} // end of selection structure
} // end of inner while loop
string temp; // there must be only one operator left, if input is legal
temp.clear();
temp = temp + c_operator.top();
postfix.push( temp ); // push in the left operator to the postfix stack;
c_operator.pop(); // cleans the c_operator stack
// end of infix to postfix conversion
// output format, print out postfix expression if no error format encountered
if( ( paren_balance == 0 ) && ( opera_balance == 1 ) ) { // print postfix expression only if no error happens in input format
cout << "Postfix expression: " << postfix << endl; }
else
cout << "Postfix expression: ";
// change of line, get ready to read a new expression on next line
while( isspace( cin.peek() ) ) {
char discard;
cin.get( discard );
}
// following part is to evaluate the solution: double, int, variable, all considered
if( flag ) { // evaluate numerically only if all arguments consists of merely digits or floating point
Stack<double> eval_d; // stores the digit in int or double type
Stack<string> storage; // stores the data in reverse sequence
eval_d.clear(); // clean the space
storage.clear();
cout << "Postfix Evaluation: " << postfix << " = ";
while( !postfix.empty() ) {
// pour data reversely from postfix stack to storage stack
storage.push( postfix.top() );
postfix.pop(); // clean the memory by the way
} // reversely store the data from postfix to storage;
while( !storage.empty() ) {
double a; double b; // a, b are operand pairs
switch( IsTokenOperator( storage.top() ) ) {
case '*':
a = eval_d.top();
eval_d.pop();
b = eval_d.top();
eval_d.pop();
eval_d.push( b * a );
break;
case '/':
a = eval_d.top();
eval_d.pop();
b = eval_d.top();
eval_d.pop();
eval_d.push( b / a );
break;
case '-':
a = eval_d.top();
eval_d.pop();
b = eval_d.top();
eval_d.pop();
eval_d.push( b - a );
break;
case '+':
a = eval_d.top();
eval_d.pop();
b = eval_d.top();
eval_d.pop();
eval_d.push( b + a );
break;
case 'N':
double d = stod( storage.top() );
eval_d.push( d ); // by using stod of <string>,
// string can be converted to floating number
break;
} // end of switch case
storage.pop(); // move the next double in stack to top
if( storage.empty() )
cout << eval_d << endl;
} // end of while loop
} // end of numerical case
else { // otherwise, the expression contains non-digit characters
cout << "Postfix Evaluation: " << postfix << " = " << postfix << endl;
} // end of variable case
// error report:
if( opera_balance < 1 )
cout << error1;
else if( opera_balance > 1 )
cout << error2;
else if( paren_balance != 0 )
cout << error3;
} // end of outer-most while-loop
return 0;
} // end of main
void skip_space() {
char discard;
while( ( cin.peek() == ' ' ) || ( cin.peek() == ' ' ) ) { cin.get( discard ); }
}
void read_operand( Stack<string>& st, bool& flg, bool& flg1 ) {
string c_operand;
// store the current operand this was read in, initialize empty
c_operand.clear(); // first, empty the input string;
while( isdigit( cin.peek() ) || isalpha( cin.peek() ) || ( cin.peek() == '_' ) || ( cin.peek() == '.' ) ) {
// if the input is an alphabet/digit/'_'/'.', concatenate it to *this string-operand
char buffer;
cin.get( buffer );
if( ( buffer == '_' ) || isalpha( buffer ) ) { flg = false; }
if( buffer == '.' ) { flg1 = true; }
c_operand = c_operand + buffer;
}
st.push( c_operand );
}
int priority( char a ) {
int precedence;
switch( a ) {
case '*':
precedence = 2;
break;
case '/':
precedence = 2;
break;
case '+':
precedence = 3;
break;
case '-':
precedence = 3;
break;
case '(':
precedence = 0;
break;
case ')':
precedence = 1;
break;
}
return precedence;
}
bool IsOperator( char a ) {
return ( ( a == '*' )||( a == '/' )||( a== '+' )||( a == '-' ) );
}
char IsTokenOperator( string& s ) {
if( s.size() == 1 )
{
char a = std::move( s[0] );
if( IsOperator( a ) )
return a;
else if( isdigit( a ) )
return 'N';
else
return 'E'; // error case, double check
}
else
return 'N'; // 'N' denotes being an operand
}
----------------------------------------------------------------------
test_stack1.cpp
----------------------------
#include <iostream>
#include <cstdlib>
#include "stack.h"
using namespace std;
using namespace cop4530;
int main() {
Stack<int> intstk;
cout << "inserting 10 elements" << endl;
for (unsigned int i = 0; i < 10; ++i)
intstk.push(i);
cout << "Size: " << intstk.size() << endl;
cout << "elements: " << intstk << endl;
cout << "emptying the stack" << endl;
while (!intstk.empty()) {
cout << intstk.top() << " ";
intstk.pop();
}
cout << endl;
cout << "Size: " << intstk.size() << endl;
cout << "inserting 10 elements" << endl;
for (unsigned int i = 0; i < 10; ++i)
intstk.push(i);
Stack<int> intstk1(intstk);
Stack<int> intstk2;
intstk2 = intstk;
// cout << intstk << endl;
// cout << intstk1 << endl;
// cout << intstk2 << endl;
if (intstk1 == intstk2)
cout << "Equal stacks" << endl;
else
cout << "ERROR: stacks are not equal" << endl;
intstk1.pop();
if (intstk1 == intstk2)
cout << "Error: equal stacks" << endl;
else
cout << "Stacks are not equal" << endl;
if (intstk1 <= intstk2)
cout << "intstk1 is less than or equal to intstk2" << endl;
else
cout << "ERROR: wrong comparision" << endl;
return(EXIT_SUCCESS);
}
--------------------------------------------------------------------
stack.h
------------------------
#ifndef LIST_STACK_H
#define LIST_STACK_H
#include<iostream>
#include<list>
namespace cop4530 {
template<typename T>
class Stack
{
public:
// zero-argument constructor
Stack();
// destructor
~Stack();
// copy constructor
Stack( const Stack<T>& a );
// move constructor
Stack( Stack<T> && a );
// copy assignment operator=
Stack<T>& operator=( const Stack<T>& a );
// move assignment operator=
Stack<T>& operator=( Stack<T> && a );
// end of default constructor, as well as "the BIG five"
// true, if Stack<T> contains no elements, false otherwise
bool empty() const;
// delete all elements from the Stack<T>
void clear();
// add x to the Stack structure, copy version
void push( const T& x );
// add x to the Stack structure, move version
void push( T && x );
// remove and discards the most recently added element (at top of stack)
void pop();
// returns a reference to the most recently added element ( at the top of stack ), as a modifiable L-value
T& top();
// accessor, returns the const reference of the most recently added element
const T& top() const;
// returns the number of elements stored in the Stack<T>
int size() const;
// print elements of Stack<T> in of sequence of their being added, first added first printed. every two elements seprated by ofc
void print( std::ostream& os, char ofc = ' ' ) const;
private:
std::list<T> lst;
};
// non-member global functions
// invokes the print() method to print the Stack<T> a in the specified ostream
template<typename T>
std::ostream& operator<<( std::ostream& os, const Stack<T>& a );
// return true if the two compared Stacks have the same elements, in the same order; otherwise false
template<typename T>
bool operator==( const Stack<T>& a, const Stack<T>& b );
// opposite to the case ==
template<typename T>
bool operator!=( const Stack<T>& a, const Stack<T>& b );
// return true if every elements in Stack a is smaller than the corresponding elements of Stack b
template<typename T>
bool operator<=( const Stack<T>& a, const Stack<T>& b );
#include "stack.hpp"
} // end of namespace cop4530
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.