Objectives
- Use an associative array (map)
- Use queues
- Create a finite state machine that can parse arithmetic expressions into tokens
- Implement a complex algorithm using C++
The objectives for this assignment are to use associative arrays (maps in this case), a queue, and an extended finite state machine to parse a string containing an arithmetic expression into tokens and place those tokens into a queue for further processing. The next assignment translates the expression from the current infix notation into postfix notation, and then evaluates the postfix expression. Tests should be done to make sure your program works properly before submitting it for grading. Notice that output from a sample run has been provided.
This assignment looks difficult at first, but the steps that are laid out are detailed. You are likely to have a few questions, but the assignment should primarily be a translation exercise from pseudocode into C++. I'll be available to answer questions, provide guidance, and check out your code as it develops to help debug it and get it running.
There are three user-defined classes and the main program that make up this assignment.
Finite state machines are a concept that is often used in computer programming. You may even have done something equivalent or similar without even realizing it. The basic idea is that there are a finite number of states. You begin in one particular state and start processing input. Each state has rules for what it will do with different types of input. As input is read, the appropriate rule is looked up based on the current state and the input that was read. The rule describes what actions should be taken and the next state to move into. This assignment uses an extended finite state machine (a finite state machine with memory) to parse tokens in an input stream and output them to a queue. The basic diagram for this state machine, without the associated actions, is shown below.
A template is available so you can start with the Token, FSM, and FSMRule classes. It is located at infixStart.txt.
This is what you have to write to do all the work. You can start by grabbing the template for the assignment and renaming it infixTokenizer.cpp. This assignment uses maps, a queue, and implements a finite state machine. There are three global variables and seven functions you have to implement.
Note: In the pseudocode below, you may see something like: if rule.actions includes FSM::ERROR. That means that you are actually checking a bit in rule.actions to see if it is set. Fortunately, there are constants already set up in the FSM class to make this easy. Here's the code that would check rule.actions to see if it includes FSM::ERROR: if ((rule.actions & FSM::ERROR) != 0) { ... }
Note: Adding a new Token to the infixQueue involves creating the Token and then adding it. Here's how you would add a new Token using: Token::OPERAND, operand, 0, true Token tkn(Token::OPERAND, operand, 0, true); infixQueue.push_back(tkn);
This is the method that does most of the work. It has two main loops, one nested inside the other. The outer loop keeps getting one line of input at a time from the user. The inner loop processes one character at a time from the input data.
cout << "Enter an expression to evaluate (or QUIT to exit)\n"; if (DEBUG) cout << "Program is in DEBUG mode\n";
This is a pretty simple function whose job is to return true if an operator is left associative, and false if it isn't. The associativities are already stored in the leftAssociative map, which makes this routine rather short.
This is a pretty simple function whose job is to return the integer precedence value of an operator. The precedences are already stored in the precedences map, which makes this routine rather short.
This is a pretty straight-forward function. It just has to add the following key/value pairs to the precedences map.
This is a pretty straight-forward function. It just has to add the following key value pairs to the leftAssociative map.
This method is simple. Print "Error: " followed by the msg passed in, followed by a newline. Then end the program.
The initFSM function has to add rules to the state machine. Keep in mind that you already have a function named put that is part of the FSM object which you can use for this task. You also have an FSM object referred to by a variable named fsm. The rules in the list below are in the following format: state, character type, actions, next state.