- In C Stktest Cpp Include Stack H Include Iostream Using Namespace Std Int Main Stack Stk Push 1 1 (324.69 KiB) Viewed 29 times
#include "Stack.h"
#include <iostream>
using namespace std;
int main () { Stack stk;
// push 1, 2, 3, 4, 5 for (int i = 1; i <= 5; i++) { stk.push(i); cout << "push " << i<< endl; }
// pop top two for (int i = 0; i < 2; i++) { int x = stk.pop(); int y = stk.peek(); cout << "pop " << x<< ", top " << y << endl; }
// push 6, 7, 8, 9, 10 for (int i = 6; i <= 10; i++) { stk.push(i); cout << "push " << i<< endl; }
// pop all while (!stk.isEmpty()) { int x = stk.pop(); cout << "pop " << x<< endl; }
return 0;}
Stack.h
// Desc: Implementation of an int sequence with push/pop in aLIFO orderclass Stack {
private:
// Desc: arr = static array ofcapacity STACKCAP // size =the number of elements presently in the stack // Inv: Follows the A2Spec, namely that the stack elements // are inorder within A[0..size-1], where the top of // the stackis A[0]. static const unsigned STACKCAP =8; int arr[STACKCAP]; unsigned size;
public:
// Desc: Objectconstructor // Post: Stack();
// Desc: Insert element x to thetop of the stack. // Pre: // Post: void push(int x);
// Desc: Remove and returnelement at the top of the stack. // Pre: // Post: int pop();
// Desc: Return the topmostelement of the stack. // Pre: // Post: int peek() const;
// Desc: // Post: bool isEmpty() const;
};
Stack.cpp
#include "Stack.h"
#include <stdexcept>
- In C Stktest Cpp Include Stack H Include Iostream Using Namespace Std Int Main Stack Stk Push 1 2 (234.49 KiB) Viewed 29 times
- In C Stktest Cpp Include Stack H Include Iostream Using Namespace Std Int Main Stack Stk Push 1 3 (156.4 KiB) Viewed 29 times
#ifndef _SCANNER_H_
#define _SCANNER_H_
#include <iostream>#include <string>
///////////////////////////////// TokenType// // symbols: +, -, *, /, (, )// literals: integer// special: eof, err///////////////////////////////typedef enum { pltok, mitok, asttok, slashtok, lptok, rptok,integer, errtok, eof }TokenType ;
//---------//// Token ////---------//class Token { public: TokenType tt; std::string text; int val;};
// Desc: Display a Tokenstd::ostream &operator<<(std::ostream &lhs, Token&rhs);
// Desc: Token scanner. Given an input stream, will return asequence// of Tokens via successive calls to.getnext();class Scanner { private: int line; std::istream *str; char buf[2]; public: Scanner(std::istream &str); Token getnext();};
#endif // _SCANNER_H_
Stack.h
// Desc: The usual fare. Descriptions, invariants,pre and post are// omitted because they are duplicatedelsewhere, namely Question 1.template <class T>class Stack { class Node { public: T data; Node *next; }; private: Node* head; public: Stack(); ~Stack(); void push(T x); T pop(); T peek(); bool isEmpty();};
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <class T> Stack<T>::Stack() { head = NULL;}
template <class T> void Stack<T>::push(T x) { Node *newhead = new Node; newhead->data = x; newhead->next = head; head = newhead;}
template <class T> T Stack<T>::pop() { T ret = head->data; Node *old_head = head; head = head->next; delete old_head; return ret;}
template <class T> T Stack<T>::peek() { return head->data;}
template <class T> bool Stack<T>::isEmpty() { return (head == NULL);}
template <class T> Stack<T>::~Stack() { Node *p = head; while (p != NULL) { head = head->next; delete p; p = head; }}
eval.cpp
#include "Scanner.h"#include "Stack.h" // GENERIC STACK
#include <iostream>
using namespace std;
int main () { Scanner S(cin); Token t;
Stack<Token> numstack, opstack; // 2xStacks of type Token
t = S.getnext();
// pretty printer coding demo. please removebefore coding while (t.tt != eof) { if (t.tt == integer || t.tt == lptok ||t.tt == rptok) { cout << t; } else if (t.tt == pltok || t.tt ==mitok || t.tt == asttok || t.tt == slashtok) { cout << ' '<< t << ' '; }
t = S.getnext(); }
cout << endl; // end pretty printer
return 0;}
Scanner.cpp
#include "Scanner.h"
using namespace std;
// Desc: Util: string + charstring operator+(string &lhs, char &rhs) { char c[2]; c[0] = rhs; c[1] = 0; return lhs+c;}
// Desc: Display a Tokenostream &operator<<(ostream &os, Token &rhs){ if (rhs.tt == eof) os << "eof"; else if (rhs.tt == errtok) os << "err"; else if (rhs.tt == integer) os <<rhs.val; else os << rhs.text;
return os;} // os << Token
// Desc: ConstructorScanner::Scanner(istream &str) { this->str = &str; buf[0] = buf[1] = 0;}
// Desc: Util: Test for newlineint newl(char c) { return (c == '\n'); }
// Desc: Return the next tokenToken Scanner::getnext() { Token ret; ret.text = ""; if (buf[0] == 0) { buf[0] = str->get(); }
// collapse whitespace while (isspace(buf[0]) || (buf[0] == 13) || (buf[0]== '\n')) { buf[0] = str->get(); if (str->eof()) break; }
// case 1: eof if (str->eof()) { ret.tt = eof; ret.text = "";return ret; }
// case 2: numerical- [0-9]+ if (isdigit(buf[0])) { ret.tt = integer; ret.text = buf; buf[0] = str->get(); while (isdigit(buf[0])) { ret.text += buf; buf[0] =str->get(); } ret.val = stod(ret.text, NULL); if (isspace(buf[0]) || (buf[0] == 13)|| (buf[0] == '\n')) buf[0] = 0; return ret; }
// case 3: symbol ret.text = buf; if (buf[0] == '+') { ret.tt = pltok; buf[0] = 0;} else if (buf[0] == '-') { ret.tt = mitok; buf[0] = 0;} else if (buf[0] == '*') { ret.tt = asttok; buf[0] =0; } else if (buf[0] == '/') { ret.tt = slashtok; buf[0] =0; } else if (buf[0] == '(') { ret.tt = lptok; buf[0] = 0;} else if (buf[0] == ')') { ret.tt = rptok; buf[0] = 0;} else { ret.tt = errtok; buf[0] = 0; } return ret;}
Marking Criteria: For all problems, your solutions will be judged by how appropriately you solved the problem. That includes not just the correctness and efficiency of your code, but also how your code is presented, i.e., coding style. The best code contains class invariants, assertions, preconditions, postconditions, and descriptions of your algorithms, written in a high-level voice. Follow the instructions carefully. Changing header files is particularly hazardous because your code may not build when we try to test it. Code that doesn't build never receives a mark much higher than 0. 0. [0 marks] Care Package Download Download the care package and unzip it. It contains your base code. 1. [30 marks] Static Array Stack The overall goal of this question is to implement a Stack ADT using a static array where • all k stack elements are stored sequentially in indices 0, 1, ..., k − 1 of the array; and the topmost element is pushed to index 0 of the array. This will be different than the typical implementation where the elements were pushed to the other end of the array. We're not suggesting this is a particularly good choice of implementation, that is, it will force at least one of push/pop to have a linear number of steps, where usually it would be O(1). What You Need to Write You are going to complete the implementation of a Stack ADT with a concrete data structure. That data structure is a static array as described in the preamble. A new Stack has no elements. Pushed items are inserted at index 0, and likewise, popped items will be removed from index 0. You will write reasonable descriptions, preconditions and post conditions. Should any of .push(x), .pop(), .peek () violate a precondition, your method should trigger an exception of type std::logic_error, with an appropriate error log message of your design. Students who submit an alternate implementation will receive 0 for this question. Complete your implementation in Stack.h and Stack.cpp, and then submit them. 2. [10 marks] Running-Time Analysis Referring to the proposed implementation in Question 1, analyze the total running time required to push n items to the Stack. Next, analyze the total running time required to pop those n items from the Stack. State your conclusions using the big-O notation. A detailed analysis is expected, i.e., if you present a final big-O answer only, you will be unhappy with your grade. Submit your analysis in Analysis.pdf.
3. [30 marks] Evaluating Infix Expressions Though a stack can be employed to calculate expressions in postfix notation, the reality is most humans don't write expressions that way: we tend to use infix notation. There is an algorithm to calculate infix expressions as well, and it requires two stacks: one for numbers and the other for operators. Decisions are made based on the next input token T (either a number, an operator or EOF) and the top of the operator stack as follows: while T is not EOF or the operator stack is non empty if T is a number: push T to the number stack; get the next token else if T is a left parenthesis: push T to the operator stack; get the next token else if T is a right parenthesis: if the top of the operator stack is a left parenthesis: pop it from the operator stack; get the next token: else: pop the top two numbers and the top operator perform the operation push the result to the number stack else if T is +, - or EOF: if the operator stack is nonempty and the top is one of +, *, /: pop the top two numbers and the top operator perform the operation push the result to the number stack else: push T to the operator stack; get the next token else if T is * or /: if the operator stack is nonempty and the top is one of *, /: pop the top two numbers and the top operator perform the operation push the result to the number stack else: push T to the operator stack; get the next token At the end of the algorithm, there should be a single number on the number stack. That is the computed answer. Your task for this problem is to code this algorithm in C++.
Specification • Your program will evaluate a single well-formed arithmetic expression from standard input, and display the result on standard output. You will implement the algorithm given above. The point of this problem is for you to use a stack to solve a problem. If you decide to solve this problem by making a system call, or by writing your own parser, etc, you will receive a grade of 0 for this question. • All input numbers are positive integers. Thus you will do integer arithmetic. • Your program may assume the input is well-formed, i.e., the behaviour may be indeter- minate on incorrect input (bad infix expressions). • Name your file eval.cpp and submit it for grading. Some Help • You are provided a Scanner class that produces Tokens for you. Please read Scanner.h to see what objects of type Token look like. • You will use the provided Stack for both your number stack and operator stack. Please check the documentation for the behaviour of .pop() before using it. • There are a few sample expressions provided to you to torture test your code. You should come up with some of your own test cases as well.