Please read the remarks about programming problems for this course.

In this assignment you will use a stack to assist in two activities:

1. language translation, to translate a simple infix arithmetic expression to postfix (also known as reverse polish notation, or RPN), and
2. arithmetic expression evaluation, to determine the value of a postfix expression.

Your program will accept an arithmetic expression typed in by the user; for example, the user might enter

3*(22 + 15) + 4*(3 + 10)

to which the program would respond with 163. The program will be a simple interpreter. An interpreter translates source code to executable code like a compiler, but an interpreter executes the translated code immediately rather than storing it in an executable file for later execution. The translation is a multipart process:

1. Lexical analysis. The input string that the user supplies consists of characters. The character + represents the addition operator, but the character 2 could, for example, represent the integer 2 or be one digit of the integer 325. The lexical analysis phase breaks the input string into higher-level conceptual units called tokens. The token + represents the addition operator, while the token 2 represents the integer 2, and the token 325 represents the integer 325. The lexical analyzer, also known as the scanner, produces a sequence of tokens from the raw input string.

2. Syntactic analysis. Lexical analysis is insufficient by itself to interpret the arithmetic expression. The token sequence (, 2, +, 2, ) represents the expression (2 + 2), but the token sequence 2, ), ( is gibberish. When presented with a legal token sequence, the syntactic analyzer, also known as the parser, constructs a representation with which the program can compute the arithmetic expression's value.

The file scanner.h (see below) defines the Token type. Our token object stores a character (symbol field) and an integer (value field). A token's symbol may be one of $, +, *, (, or ). If the token's symbol is $, the token represents an integer, and so its value field stores a valid integer value. If the token's symbol is any other character, the token's meaning is derived from its symbol; that is, + represents addition, * represents multiplication, ( represents a left parenthesis, and ) represents a right parenthesis. If the token's symbol is not $, the token's value field is meaningless.

The function scan (provided for you) converts a line of user input into a token sequence, if possible. This function is the scanner. You should use this function as is. The function expects a line that contains just non-negative integers, plus signs, asterisks, and parentheses. An acceptable input string will be an arithmetic expression in infix notation (see http://en.wikipedia.org/wiki/Infix_notation). The function's return value is a token sequence in infix notation. Any whitespace (spaces and tabs) in the original input string does not appear in the token sequence.

The code you write will deal with this infix token sequence. You must translate this infix token sequence into an equivalent postfix token sequence. The postfix sequence is devoid of parentheses, because parentheses are not necessary in a postfix arithmetic expression. Fortunately, the algorithm to perform the translation is well known and easy to implement (see below).

Once you have the postfix token sequence, you must write a function that processes the token sequence to produce an integer result. Again, the algorithm is relatively easy to implement.

Both the infix-to-postfix translation and postfix evaluation rely on one very useful linear data structure—the stack.

The complete project consists of six C++ source files:

• scanner.h is a header file declaring the fundamental types required for our expression evaluator: Token and TokenSequence. It also contains the declaration of the scan lexical analyzer function and overloaded operator<< to conveniently display the contents of tokens and token sequences. You should not modify this file.
• scanner.cpp implements the scan and operator<< functions. You should not modify this file.
• InfixToPostfix.h declares the infix_to_postfix and evaluate functions. The infix_to_postfix function produces a postfix token sequence from an infix token sequence, and the evaluate function computes an integer result from a postfix token sequence. You should not modify this file.
• main.cpp contains the code that interacts with the user. It makes use of the code in the other files. You should not modify this file.
• stack.h contains an incomplete (but compilable) implementation of a bounded generic stack abstract data type. You must complete the code within this file.
• InfixToPostfix.cpp implements the infix_to_postfix and evaluate functions. You must complete the code within this file.

Part of your task is to complete the code for a generic stack abstract data type. The incomplete stack code is found in stack.h. It defines a template class that clients can instantiate to the specific type of elements they need to store. The non-type template parameter (N) specifies the stack's maximum capacity. Since the Stack class is a template, there is no advantage to define its methods outside of the class itself.

Your stack should use a statically allocated C++ array for its storage. The non-type template parameter, N, determines the array's size. Your stack type must support at least the following operations:

• push pushes an element onto the top of the stack.
• pop pops the top element off of the stack.
• top reveals the top stack element without modifying the stack.
• full returns true if the stack is full and cannot access any more elements; othewise, it returns false.
• empty returns true if the stack contains no elements; otherwise, it returns false.

You have full control over the exact parameters and return types of these methods. You also are responsible for determining the error-checking capabilities the methods provide, if any (for example, what if the user attempts to pop an element off an empty stack or push an item onto a full stack?). Your stack implementation should be general enough so that your stack objects could be used in many different contexts.

After you have tested your stack in isolation to ensure that it behaves properly, you will use it in two different ways:

1. Use an instantiation of your stack template in an implementation of a simplified form of Edsger Dijkstra's Shunting-yard_algorithm to guide the translation of a token sequence representing an infix arithmetic expression into a postfix (RPN) token sequence. You need be concerned only with parentheses, addition, multiplication, and non-negative integers, so your code will be much simpler than the algorithm found on Wikipedia.

   Implement the infix_to_postfix function which performs the translation. Your code in this function must use a stack of tokens.

2. Use an instantiation of your stack template to evaluate a token sequence representing a postfix arithmetic expression. In this case your stack will hold integers, not tokens. The evaluation process is straighforward:
   • See a number token in the postfix token sequence? Push its corresponding integer value onto the stack.
   • See an operator token in the postfix token sequence? Pop the top two integer elements off the stack, apply the appropriate operator to the two elements, and push the resulting integer value token back onto the stack.
   • No more tokens left in the postfix token sequence? Return the value on the top of the stack.

   Implement the evaluate function which performs the translation. Your code in this function must use a stack of integers.

The requirement of using both a stack of tokens and a stack of integers demonstrates that your Stack class truly is generic.

For this assignment you do not need to worry about handling illegal arithmetic expressions the user might enter; however, you must be able to process all legal arithmetic expressions the user submits.