trjhtr

I had to implement a parser according to a given grammar as part of a school project. However, only the program execution was graded and I want to know if my code adheres to best practices. I would really appreciate it if you could give me pointers on how to improve my code.

Search conditions are of the form: a + b < 10 OR c = 1. The following code parses the search condition into an expression tree. The input to the function is a vector of the tokens in the search condition.

void recursiveSplit(node *parent, vector<string> const &tokens, string delimiter) 
 /* Given a string, parse it into an expression tree with nodes as the
 * operators and the children as the operands */
 if (tokens.size() == 1) 
 /* Base case for the recursion, the leaf nodes are either strings or
 * integers */
 node *mathNode;
 mathNode = new node(tokens[0]);
 parent->subTree.push_back(mathNode);
 return;
 else 
 vector<string>::const_iterator it;
 for (it = tokens.begin(); it != tokens.end(); it++) 
 if (*it == delimiter) 
 break;
 
 
 if (it != tokens.end()) 
 /* Case 1 :delimiter was found */
 node *delimNode;
 delimNode = new node(delimiter);
 parent->subTree.push_back(delimNode);
 vector<string> leftTokens(tokens.begin(), it), rightTokens(it+1, tokens.end());
 string newDelimiter = switchDelimiter(delimiter);
 recursiveSplit(delimNode, leftTokens, newDelimiter);
 /* In rightTokens, we still need to search for the current
 * delimiter since we may have multiple instances of the delimiter
 * */
 recursiveSplit(delimNode, rightTokens, delimiter);
 else 
 // delimiter is not found
 string newDelimiter = switchDelimiter(delimiter);
 recursiveSplit(parent, tokens, newDelimiter);
 
 


string switchDelimiter(string delimiter) 
 /* Return the next delimiter based on the priority. The priority of
 * operations is : OR, AND, <, >, =, +, -, * */
 char delim;
 if (delimiter == "OR") ';
 else if (delimiter == "AND") 
 delim = '&';
 else 
 delim = delimiter[0];
 

 switch(delim) ':
 return "AND";
 case '&':
 return "<";
 case '<':
 return ">";
 case '>':
 return "=";
 case '=':
 return "+";
 case '+':
 return "-";
 case '-':
 return "*";
 case '*':
 return " ";
 


node *createTree(const string& searchStrBuf) 
 string buf;
 stringstream ss(searchStrBuf);
 vector<string> tokens;
 while(ss >> buf) 
 if ((buf != ")") && (buf != "(")) 
 tokens.push_back(buf);
 
 
 node *root = new node("searchTreeRoot");
 recursiveSplit(root, tokens, "OR");
 return root;


class node 
 public:
 string nodeType;
 vector<node *> subTree;

 node(string strNodeType) 
 nodeType = strNodeType;
 
;

You don't show how this is being called. So we have to make some assumptions:

1. I assume that the search conditions have been parsed into tokens as one-token-per-string in the vector? That is, for search conditions like "a + b < 10 OR c = 1" (your example), the tokens vector looks like "a", "+", "b", "<", "10", "OR", "c", "=", "1" .




2. I assume that the node type contains a vector<node *> called subTree.




3. You also don't specify if you expect the resulting tree to be a binary tree or not. Your code is written that way, but it doesn't seem to be a requirement. Other than the relational operators, the rest of your operators could easily handle more than two operands: a OR b OR c, 1 + 2 + 3, etc. I assume that the tree must be binary, since you coded it that way.

With those assumptions, I observe:

1. You are not handling the case of a zero-length tokens vector. This would be an empty input, or an error of some kind.




2. You are not handling syntax errors at all, really. What should your code be returning for something like a + * b?




3. You are using recursion when it is not necessary. Specifically, your switchDelimiter function is really just a way to hide iteration. It would be better, IMO, to write your code to loop over the delimiters instead of calling a function and then recursing with the same tokens and a new delimiter.




4. You are using recursion when it is not necessary. Specifically, your "right subtree" case recurses with the same delimiter, and it + 1. That's a sign that you can just continue your existing loop, after updating the parent node to a new value. (You will have to move your "new node" code inside the loop, though.)


3.