Implementing an expression
evaluator using vectors and stacks
Specification:
Implement
an arithmetic evaluator that can evaluate any valid arithmetic expression
composed of real numbers (such as 2.4, 5, …), arithmetic operators (only +, -,
*, /), and parentheses. You program should be able to repeatedly do the
following:
- ask the user
to type in an infix arithmetic expression and read that expression from
the keyboard into a character array,
- process the
character array to retrieve and store the expression as a series of token
strings in a vector of strings, where each token string should correspond
to a real number, an arithmetic operator, a right parenthesis, or a left
parenthesis,
- with the help
of a stack (of strings), then process the array of strings to determine
the corresponding postfix expression and store the postfix expression as a
separate vector of token strings,
- with the help
of a stack (of floating-point doubles), you should then evaluate the
postfix expression (as a vector of token strings) to get and report the
value of the infix expression given by the user.
What to do:
- Download
the code framework and Play with the sample executable: First you should download this zip file
and unzip it to get a sample executable and an unfinished code framework
for implementing an arithmetic expression evaluator. Play with the
executable to see how the fully implemented expression evaluator cqn
evaluates concrete arithmetic expressions.
- Study
the TokenAnalyzer class: Carefully study the TokenAnalyzer class as defined in simpleTokenizer.h and implemented in simpleTokenizer.cpp. The static method getTokensFromOneCharArray of the TokenAnalyzer class allow you to the charaters in a
character array into a series of token strings stored as a vector of
strings. The other four static
methods of the TokenAnalyzer
class: isNUMERICAL_LITERAL,
isNUMERICAL_OP, isLEFT_PARENTHESIS, isRIGHT_PARENTHESIS, allow you to
determine whether a token is a numerical constant, an operator, a left
parenthesis, or a right parenthesis. You do not need to change anything in
simpleTokenizer.h and simpleTokenizer.cpp.
- Study
the SimpleEvaluator class: Carefully study the SimpleEvaluator class as defined in simpleEvaluator.h and partially implemented in simpleEvaluator.cpp. The static
method getPrecedenceLevel of the SimpleEvaluator
class returns the precedence levels of the operators. The static method infixToPostfix of the SimpleEvaluator
class derives the corresponding postfix expression from a given infix
expression. The static method evaluatePostfixExpression of the SimpleEvaluator
class evaluate the value of a given postfix expression.
- Study
the code in main.cpp: Carefully
examine the code in main.cpp to see how you can repeatedly use the TokenAnalyzer class and the SimpleEvaluator class to
(i) read an infix arithmetic expression from the keyboard
into a character array, (ii) get the
individual tokens as a vector of strings, (iii) determine the
corresponding postfix expression, (iv) evaluate the postfix expression to
determine the value of the arithmetic expression .
- Fully implement the SimpleEvaluator class: You have to complete the implementation of the infixToPostfix method and the evaluatePostfixExpression method of the SimpleEvaluator class in simpleEvaluator.cpp.
- Carefully
test your implementation of the SimpleEvaluator class: Extensively test your implementation to make sure it can correctly
handle all valid arithmetic expressions.
About infix-postfix conversion and postfix expression evaluation
using stacks:
- Infix
expressions (e.g. 2+3*4):
each binary operator (e.g. +) is written between the two operands (e.g. 2
and 3*4) and we need to carefully take care of the precedence levels of
different operators when evaluating an infix expression (e.g. the
multiplication operator * has a higher precedence level and 3*4 must be
evaluated before applying the multiplication operator +).
- Postfix
expressions (e.g. 2 3 4 *
+): each binary operator (e.g. +) is written between the two operands
(e.g. 2 and the result of 3 4 *) and we do not need to care about the
precedence levels of different operators when evaluating a postfix
expression from left to right.
- How
to evaluate an infix expression: convert it into a postfix expression first and then evaluate the
postfix expression.
- What
is a stack: it is a data
structure for adding and removing items in a first-in-last-out fashion. Operationally, it is like a C++
vector constrained to the following methods
- push_back(
x) : adds an
additional element x to the end
of the vector;
- pop_back( )
: deletes the
element at the end of the vector;
- back( ) : returns (a reference to) the last
element of the vector;
- clear( ) : erases
all the elements of the vector to make it an empty vector;
- empty( ) : return true if
the vector is empty; return false
if the vector is not empty.
More technical references:
- Converting strings to numerical
values: For converting a numerical constant store as a string token
into its corresponding numerical value, please see how to use the
c_str() method of C++ string class to get a corresponding C style
string stored in a character array, and how
to use atof( ) to get the numerical value from a number stored as a
character string in a C-style character array.
- Using the template stack class in C++
standard template library: For infix-postfix conversion and for
evaluating postfix expressions, you need to use stacks. This can be
accomplished by using a vector to simulate a stack as described earlier above.
Alternatively, you can also directly use the C++ stack template class
provided in the C++ standard template library. See the description of C++
standard template for stacks and some sample code here
to understand the use of the member functions: pop,
push, top, and empty.