联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981
Lab 1: Stack Application
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
GenericStack
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
method to print the GenericStack
bool operator== (const GenericStack
compared “GenericStack”s have the same elements, in the same order.
bool operator< (const GenericStack
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: 8934
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.
Submit Lab 1 to the Assignment box no later than Sunday 11:59 PM EST/EDT.Elements
Criteria
Score
Not Attempted
(Criterion is
missing, not in
evidence, or fails
to meet minimum
requirements.)
Novice
(Does not meet
expectations;
performance is
substandard.)
Basic
(Works towards
meeting
expectations;
performance needs
improvement.)
Proficient
(Meets
expectations;
performance is
satisfactory.)
Exemplary
(Exceeds
expectations;
performance
is
outstanding.)
Completeness and
correctness of the
report.
0-11
12-13
14-15
16-17
18-20
/20
Code documentation.
0-10
11
12
13
14-15
/15
Development and
correctness of the
application.
0-11
12-13
14-15
16-17
18-20
/20
Development and
correctness of sorting
methods.
0-24
25-29
30-34
35-39
40-45
/45
发表评论