Class Name: FSM
Method Name: runFSM
Paramaters: String String String[]
Returns String[]
Implement a class FSM, which contains a method runFSM. The method runs an
augmented finite state machine:
The augmented finite state machine consists of a number of states. Each state
has a unique name of type String. There are edges connecting the states.
These edges are directional: they go in only one direction, their source state
to their sink state (source and sink states are described below). Each edge
has a corresponding symbol and function that are both represented as Strings.
Here is the method signature (be sure your method is public):
String[] runFSM(String symbols, String states, String[] edges)
Input:
*symbols - The first parameter to runFSM is a String containing elements
referred to as symbols that will be passed to the FSM. The elements/symbols
will contain letters only (A-Z and a-z, inclusive). Each element of the
symbols input parameter is separated by one or more spaces.
*states - The second parameter to runFSM is a String containing elements that
refer to the names of the states. The names/states will contain letters (A-Z
and a-z, inclusive) only. The first state in this list is the starting state.
Each element of the states input parameter is separated by one or more spaces.
*edges[] - The third parameter is a String[]. Each element in the String[]
describes an edge. The Strings in the array will contain four sets of letters,
where the sets are separated by one or more spaces. Parsing the String from
the left-most character moving right, the first set of letters is the source
state - the state in which the edge starts. The second set of letters is the
sink state - the state in which the edge ends. The third set of letters is the
symbol corresponding to the edge. The fourth set of letters is the function
corresponding with the edge.
Output:
The output is a String[] containing a list of all the functions called with
their associated symbols as parameters, in order. There should be only one
element in the output for each symbol in the first input String.
The augmented finite state machine is passed a sequence of symbols. Each
symbol is processed as follows:
1. Use the first state (the first element of the states String) as the source
state and let that equal the current state.
2. Determine the first symbol (i.e. the first element of the symbols String)
let that equal the current symbol.
3. Find the edge of the current state that corresponds to the current symbol.
4. Add a String to the output array. The String should consist of the
function name of the edge found in step 3 with the current symbol enclosed in
parentheses (i.e. if the function is "open" and the symbol is "hi", the
function call is "open(hi)").
5. Move to the sink state that corresponds with the current symbol.
6. Let current state be equal to the sink state from step 5
7. Repeat steps 3 - 6 for the remaining symbols.
Note:
* If ever there is no edge leaving the current state with the current symbol,
add the String "ERROR" to the output array, remain at the current state, and go
on to the next symbol.
* No two edges may contain the same source state and symbol.
* All String comparisons are case sensitive.
* The output is a list of the function calls created in step four (above) in
order.
* The sink state can be equal to the source state
* There may be additional spaces at the beginning or end of any input String.
TopCoder will ensure:
- All the Strings and elements of arrays will contain letters (A-Z and a-z,
inclusive) and spaces (' ') only.
- The states mentioned in the edges array will be present in the states String.
- symbols will contain at least one element.
- states will contain at least one element.
- symbols and states will have length between 1 and 50, inclusive.
- edges will contain between 1 and 50 elements, inclusive, and each element
will contain between 1 and 50 characters, inclusive.
- No two edges will have the same source state and symbol
- Elements of the edges array will be well formed. That is, each element will
be in the form: "(source state) (sink) (state symbol) (function)" (the
parentheses are for clarity and should not be included in the String). There
will be exactly four elements separated by one or more spaces
Examples:
Example relating to a vending machine that releases candy every time 20 cents
is put in, assume:
states="Zerocents Fivecents Tencents Fifteencents Twentycents"
and
edges={
"Zerocents Fivecents nickel needMoreOne",
"Zerocents Tencents dime needMoreTwo",
"Fivecents Fifteencents dime needMoreThree",
"Fivecents Tencents nickel needMoreFour",
"Tencents Fifteencents nickel needMoreFive",
"Tencents Twentycents dime releasingCandyOne",
"Fifteencents Twentycents nickel releasingCandyTwo",
"Fifteencents Twentycents dime releasingCandyThree",
"Twentycents Fivecents nickel needMoreSix",
"Twentycents Tencents dime needMoreSeven"
}
If symbols="nickel dime dime", the output should be:
{"needMoreOne(nickel)",
"needMoreThree(dime)",
"releasingCandyThree(dime)"}
If symbols="dime oops dime" the output should be
{"needMoreTwo(dime)",
"ERROR",
"releasingCandyOne(dime)"}
If symbols="dime nickel dime dime dime nickel" the output should be
{"needMoreTwo(dime)",
"needMoreFive(nickel)",
"releasingCandyThree(dime)",
"needMoreSeven(dime)",
"releasingCandyOne(dime),
"needMoreSix(nickel)}
More Examples:
If symbols=" a a a b b c" and
states=" stateZero stateOne stateTwo"
and edges=
{"stateZero stateOne a doSomething",
"stateOne stateTwo b doNothing",
"stateTwo stateZero c doEverything"}
The output should be
{"doSomething(a)",
"ERROR",
"ERROR",
"doNothing(b)",
"ERROR",
"doEverything(c)"}
|