Word Ladder is a word game where you are given two words and must transform one into the other by changing one letter at a time, such that each change results in a valid word. For example if we want to change "four" into "five" we can do so in six steps via: four-tour-torr-tore-tire-fire-five (torr is a unit of pressure). Given two words, we want to find the minimum number of moves it takes to change one into another, or determine that it is not possible to do so. You can play this game online here. We will use the same list of valid four letter words (the provided file 4words.txt) that is used by this website. Given a list of valid four letter words, we can construct an associated graph. There is a vertex for every word on the list. Two vertices are connected by an edge if and only if they differ by just one letter. In other words, if two vertices are connected by an edge, we can move from one to the other in one step in a word ladder. Finding the optimal solution to a word ladder then amounts to finding a shortest path in this graph. In this challenge, you will write a function that given two four letter words will find a shortest path between them, that is will optimally solve the word ladder game (or say that there is no path between the words) for any two given input words. We let you choose the data structure you want to use to store the word graph. You can make any additions to wordLadder.hpp you need to accommodate your design (this includes member variables and member functions). You can also add any other libraries you may need. Note that as usual your member functions should be implemented in wordLadder.cpp. In addition to finding shortest paths we ask you to implement several other primitives on this graph. Let's look first at the easy member functions in wordLadder.hpp , which are addVertex, addEdge, isVertex, isEdge, and removeVertex. All of addVertex, addEdge, isVertex, isEdge should work in � ( log ⁡ � ) O(logN) time where � N is the number of vertices. removeVertex should work in time � ( � log ⁡ � ) O(DlogN) where � D is the number of neighbors of the vertex being removed. class WordLadder { private: // put whatever member variables you want to represent the graph here public: // default constructor doesn't have to do anything WordLadder(); // construct word graph from words given in filename explicit WordLadder(const std::string& filename); // add vertex a to the graph with no neighbours if a is // not already a vertex. Otherwise, do nothing. void addVertex(const std::string& a); // if both a and b are vertices in the graph then add // an edge between them. Otherwise do nothing. void addEdge(const std::string& a, const std::string& b); // check if there is an edge between words a and b bool isEdge(const std::string& a, const std::string& b) const; // check if a is a vertex bool isVertex(const std::string& a) const; // remove vertex a from the graph void removeVertex(const std::string& a); ... }; Most of these are self-explanatory. One design decision we made which you will have to follow is that addEdge(a, b) will only add an edge between a and b if they are both already vertices in the graph. The main event is to implement the getShortestPath function. The running time of this function should be � ( � ) O(E), where � E is the number of edges in the graph. Note that if there is no path between the two input words you should return an empty vector. // solve the word ladder problem between origin and dest. // output a vector whose first element is origin, last element is dest, // and where each intermediate word is a valid word and differs from the // previous one by a single letter. Moreover the size of this vector // should be as small as possible, i.e. it lists vertices on a shortest // path from origin to dest. If there is no path between origin and dest // return an empty vector. std::vector getShortestPath(const std::string& origin, const std::string& dest); Another interesting function to implement is listComponents. This returns a std::map. The size of this map is the number of connected components in the graph. For each connected component there is a std::pair where the first element of the pair is an example word in that connected component, and the int is the number of words in that connected component. The example word can be any word in the connected component. The running time of this function should be � ( � + � log ⁡ � ) O(E+NlogN) where � E is the number of edges and � N is the number of vertices. // compute all the connected components in the graph. The output is // a std::map. The size of the map should be the // number of connected components. For each connected component give the // name of a word in the connected component (the std::string part of the // pair) and the number of words in that connected component (the int part). std::map listComponents();

The first part of assignment 2 is a continuation of the Stack Calculator you built in Tutorial Week 6. There you wrote a program that evaluated an arithmetic expression given in postfix notation, like 3 5 +, instead of more familiar infix notation, like 3 + 5. In this part of the assignment you will complete the construction of a calculator for infix expressions by writing a function to convert an infix arithmetical expression into a postfix one. Here is the important part of the calc.hpp header file: namespace Calc { // type is either '+', '-', '*', '/' for the operators or 'n' to indicate a number // in the case of a number val holds its integer value. struct Token { char type {}; int val {}; }; std::vector tokenise(const std::string&); std::vector infixToPostfix(const std::vector&); int evalPostfix(const std::vector&); int eval(const std::string&); } // namespace Calc The function tokenise takes a string of an arithmetic expression like "(3+5) * 2 - 3" and outputs a vector of Tokens. A Token has 2 parts. The first part is a char that represents the token type. It is one of the operators '+', '-', '*', '/' or 'n' to indicate that the token holds a number. In the case the Token holds a number, the second member variable, val, holds the integer value of the number. In the case of an operator the val member variable can be ignored (and is left as 0). As an example, on input "(3+5) * 2 - 3" the tokeniser function would output { {'(', 0}, {'n', 3}, {'+', 0}, {'n', 5}, {')', 0}, {'*',0}, {'n', 2}, {'-', 0}, {'n', 3} }. The function you are to implement is infixToPostfix. This function takes a vector of tokens derived from an infix expression and converts it into a vector of tokens in postfix notation. We will describe how to do this below. For now we continue reviewing the functions in calc.hpp. The function evalPostfix provided for you. This function is essentially from Tutorial Week 6 and evaluates an arithmetic expression in postfix notation. The function eval puts all the parts together to evaluate an infix expression: int Calc::eval(const std::string& expression) { std::vector tokens = tokenise(expression); std::vector postfix = infixToPostfix(tokens); return evalPostfix(postfix); } Implementation: You should implement the infixToPostfix function in the file calc.cpp. There is a famous algorithm to go from infix notation to postfix notation due to Dijkstra called the shunting yard algorithm. We describe the algorithm here and give pseudocode for it. See also the wikipedia article. Note that the wikipedia article talks about a more general situation where the expression can also contain functions like sin ⁡ � sinx. We do not have to worry about this case. In order to correctly convert an infix expression into a postfix one, it is important to note the precedence of operations. '+' and '-' have the equal precedence, and '*' and '/' have equal precedence which is greater than that of '+' and '-'. You will need to represent the precedence of all these operators somehow in your program. vector of Tokens output; vector of Tokens operatorStack; for each Token t in the input if the token is a number, push it back to the output; else if the token is '(', push it back to the operatorStack; else if the token is ')', pop tokens off of the operatorStack and push them back onto output until you reach '('. Pop '(' off the operatorStack too; else: As long as there operators on operatorStack that are not '(': if the operator at the top of the operatorStack has >= precedence to t, push it onto output and pop it off of the operatorStack. Push back t to the operatorStack. // At this point we have finished iterating over the input reverse operatorStack and append it to the end of output.

这是我大二时学习Comp6771时完成的个人项目，目的是实现对于Filtered String View以及双向迭代。 Write a more complex version of the described above - the .string_viewfiltered_string_view A is like a , however it presents a filtered view of the underlying data. This means that readers of the may only see part of the underlying data.filtered_string_viewstring_viewfiltered_string_view The filter is optionally provided by the caller as a unary predicate (a function which returns a boolean) which returns if the data is to be kept. If not provided, the filter will default to the "true" predicate, i.e., a function which always returns true. In this case, no data would be filtered.true You can see examples of this behaviour throughout the spec. You'll also be writing an iterator for this class. The iterator will be a bidirectional (as a provides a read only view into its underlying data).const_iteratorstring_view You will implement this specification in and/or , and write tests in .src/filtered_string_view.hsrc/filtered_string_view.cppsrc/filtered_string_view.test.cpp