LC 101 Symmetric tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note: Bonus points if you could solve it both recursively and iteratively.

Recursive

A tree is symmetric if the two subtrees beneath any root has:

  1. the left and right child has the same value
  2. The left child’s left matches with right child’s right
  3. The left child’s right matches with left child’s left.

The base case is when two leaf level node matches and they don’t have children.

    bool isSymmetric(TreeNode* root) {
        return isSym(root, root);
    }
    bool isSym(TreeNode* leftNode, TreeNode* rightNode){
        if(leftNode == NULL && rightNode != NULL) return false;
        if (leftNode != NULL && rightNode == NULL)return false;
        if(leftNode == NULL && rightNode == NULL) return true;
        return (leftNode -> val == rightNode -> val &&
            isSym(leftNode -> left, rightNode -> right) && 
            isSym(leftNode -> right , rightNode -> left));
    }

Improvement

In the previous code, we have three coditions to check, but observe that it only wants to know if both nodes are null or just one is null so we can do

if(leftNode == NULL && rightNode == NULL) return true;
if(left == NULL || right == NULL) return falase;

ITerative

    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        s.push(root);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode == NULL) continue;
            if(leftNode == NULL || rightNode == NULL) return false;
            if(leftNode -> val == rightNode -> val){
                s.push(leftNode -> left);
                s.push(rightNode -> right);
                s.push(leftNode -> right);
                s.push(rightNode -> left);
            }
            else
                return false;
        }
        return true;
    }

LC 100 Same tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Two tree are the same if

  1. Both root nodes are either both empty of both valid
  2. The left subtree of p is the same as the left sub tree of q
  3. The right subtree of p is the same as the right sub tree of q

So we can write a recursive code to check the above three conditions

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p != NULL and q == NULL or(p == NULL and q != NULL))return false;
        return (p->val == q->val && isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right));
    }

ITerative

DFS

To use DFS, we want to first go as deep as possible, so we use a stack to enforce FILO policy so we will always go deep with the current node and only explore other branch when the current branch hit the bottom (null on both left and right children)

    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        s.push(p);
        s.push(q);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode != NULL) return false;
            if(leftNode != NULL && rightNode == NULL) return false;
            if(leftNode != NULL && rightNode != NULL){
                if(leftNode -> val == rightNode -> val){
                    s.push(leftNode -> left);
                    s.push(rightNode -> left);
                    s.push(leftNode -> right);
                    s.push(rightNode -> right);
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }

LC95 Unique Binary Search Tree

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n < 1)
            return vector<TreeNode*>(0);
        return genRoots(1, n);
    }
    vector<TreeNode*> genRoots(int start, int end){
        vector<TreeNode*> res;
        if(start > end){
            return vector<TreeNode*>(1,NULL);
        }

        for(int i = start; i <= end; i ++){
            vector<TreeNode*>left = genRoots(start, i - 1);
            vector<TreeNode*>right = genRoots(i + 1, end);    
            //then put the connect the root with all possible left and right child
            for(int j = 0; j < left.size(); j ++){
                for(int k = 0; k < right.size(); k ++){
                    TreeNode *curRoot = new TreeNode(i);
                    curRoot -> left = left[j];
                    curRoot -> right = right[k];
                    res.push_back(curRoot);
                }
            }
        }
    return res;   
    }
};

LC 96 Unique binary search tree

We use dynamic programming. Given nodes[1,2,3….n], we could have n roots. If we calculate how many ways to arrange each root, we can just sum them up all ways.
Let’s call stores ways to arrange i nodes in uniqueShapes[i], and to calculate uniqueShapes[i], we just sum uniqueAtI[1],… till uniqueAtI[i].

To calculate uniqueAtI[j] when calculating uniqueShapes[i], j will be the root. There will be j – 1 nodes smaller than j and i – j nodes bigger than j. so j – 1 nodes will be on the left side of root j and i – j node will be on right side of root j.
There are uniqueShapes[j] ways to arrange j node and uniqueShapes[i – j] ways to arrange i – j, and arranging these two groups of nodes are not interfering with each other so we can use product rule:
While calculating uniqueShapes[i], we will iterate through 1…i as root and calculate uniqueAtI for each of them according to

uniqueAtI[j] = uniqueShapes[j - 1]* uniqueShapes[i - j]
class Solution {
public:
    int numTrees(int n) {
        vector<int> uniqueShapes(n + 1, 0);
        vector<int> uniqueShapesAtI(n + 1, 0);
        uniqueShapes[0] = 1;
        uniqueShapes[1] = 1;
        for(int i = 2; i <=n; i ++){
            int sum = 0;
            for(int j = 1; j <=i; j ++){
                uniqueShapesAtI[j] = uniqueShapes[j - 1] * uniqueShapes[i - j];
                sum += uniqueShapesAtI[j];
            }
            uniqueShapes[i] = sum;
        }
        return uniqueShapes[n];

    }

};

Learning ANTLR 4: building grammar

A language will usually follow 4 abstract patterns

  1. sequence : ( a sequence of elem, such as values in array initializer
  2. Choice: choice between mutliple alternative phrases
  3. Token dependence presence of one token requires presence of its counterpart
  4. nested phrase: self-similar language

We can use EBNF (extended backus-naur-format) to express. It will also allow use to use subrules, inline rules wrapped in parenthesis.

Parsers

Sequence

EG

#define true false 

To specify a sequence for grammar, just list the elements in order.

'#define' string string'

For arbitrarily long sequence we need to use + or *. They are subrule operator. + will encode one or more. (INT)+ will describe one of more operator. * will encode 0 or more.

Patterns within sequence

We use csv file to demonstrate two patterns

file : (row '\n')* ; // sequence with a '\n' terminator
row : field (',' field)* ; // sequence with a ',' separator
field: INT ;

terminator

the ‘\n’ token terminates each element of the sequence.

Other terminator includes

stats : (stat ';')*

Separator

Rule row use the list and match a field followed(seperated) by zero or more ‘,’ field. One more separator:

exprList : expr(',' expr)*

###zero-or-one sequence
?

(‘extends’ identifier)?

It will optionally match extend for super class.


##Choice(alternatives)
Use | as the or operator.
EG:

type :’float’ | ‘int’ | ‘void’;

<br />##Token dependency
If you see a left bracket, you better have a right bracket.
We use a sequence that specifier both symbols.

array : ‘[‘ INT+ ‘]’ ;

<br />Or 

functionDeclear : type ID ‘(‘ formalParameters? ‘)’ block // void f(int x) {…} formalParameters: formalParameter ( ‘,’ formalParameter)*; formalParameter: type ID;

<br />##Nested Phrase
self-similar language structure. expression

expr : ‘(‘ expr ‘)’ | ID;

<br />##How parsers handle precedence. 
The higher the line number, the higher the precedence.
```java
expr : expr '^'<assoc=right> expr // ^ operator is right associative
    | expr '*' expr // match subexpressions joined with '*' operator
    | expr '+' expr // match subexpressions joined with '+' operator
    | INT // matches simple integer atom
;

Lexers

There are also some very common lexical constructs:

Identifiers

ID : [a-zA-Z]+ ; // match 1-or-more upper or lowercase letters

What if a string keyword matches with ID

EG: enum can be matched with ID. But it is also a keyword that’s used in ;parser. ANTLR will seperate string literal, lexer rules and parser rules. Parser rules will be checked first, then string literal. Lexer will be checked last.

Numbers

For integer, it is easy:

INT : [0-9]+;

But float needs to consider the dot.

FLOAT: DIGIT + '.' + DIGIT* | '.' DIGIT+;

We use fragment to create reuseable rules only used by lexical rules and not a token in and itself.

fragment
DIGIT: [0-9];

String literal

dot is a wildcard that matches a single character. So .* will match any sequence of zero or more characters. But that would just go to end of file. So the ‘?’ will make the rule nongreedy. It will consume character until what follows the subrule in the lexer rule. In this case, it will stop after seeing “, the subrule right after ‘.*?’.

STRING : '"' .*? '"' ; // match anything in "..."

It consists of three parts: the string literal ” to start a string and
It is not good enough since we need escape sequence to allow special characters such as double quote inside the string.

We can define escape sequence with backslash. If we want to get double quote inside a double-quoted string, we use \”.

STRING : '"'(ESC|.)*? '"';
fragment
ESC: '\\"' | '\\\\';

In ESC, we have \ because ANTLR needs to escape as well.

Comments and whitespace

We need to discard them. Identify them the same way other Lexer rules did but tell Lexer to throw it out via -> skip.

LINE_COMMENT: '//' .*?  '\n' -> skip; //Match "//" stuff '\n'
COMMENT: '/*/ .*? '*/ -> skip;  //Match /* stuff */

Whitespace

WS :(' '| '\t' | '\r' | '\n') + -> skip;

A shorthand is:

WS: [ \t\r\n]+ -> skip;

Dealing with ambiguities

It resolve ambiguities by favoring the rule specified first. That means ID rule should be defined after keyword rules.

Learning ANTLR 3: More examples are coming

Matching arithmetic expression

An arithmetic grammar for +-x/ and parenthesis:

grammar Expr;

/** The start rule; begin parsing here. */
prog:   stat+ ;         // a program contains multiple statement
//a statement can either be expr \n or assignment \n or \n
stat:   expr NEWLINE                
    |   ID '=' expr NEWLINE        
    |   NEWLINE                   
    ;

expr:   expr ('*'|'/') expr   
    |   expr ('+'|'-') expr   
    |   INT                    
    |   ID                    
    |   '(' expr ')'         
    ;

ID  :   [a-zA-Z]+ ;      // match identifiers <label id="code.tour.expr.3"/>
INT :   [0-9]+ ;         // match integers
NEWLINE:'\r'? '\n' ;     // return newlines to parser (is end-statement signal)
WS  :   [ \t]+ -> skip ; // toss out whitespace

Some highlights

  1. Grammar consists of rules for synatctic structure and rules for vocabulary symbols(tokens).
  2. program consisits of multiple statements
  3. Seperate alternatives of a rule with |
  4. Group symbols with parenthesis into subrules(‘*’ | ‘/’)
  5. We can do left recursion(invoke itself at the start of alternative rules.

To test, we run

**$ antlr4 Expr.g4
$ javac Expr*.java
$ grun Expr prog -gui t.expr # launches org.antlr.v4.runtime.misc.TestRig**

We will see the parse tree for input in t.expr and **invoke the parser with rule prog **.

Calling a rule method is like invoking that rule. We can call any parser rule method.

Building a calculator

We need to perform some actions using parse-tree visitor.

To do so wee need to add

1.label the alternative rules so we can have different visitor per rule so we can have different event for different input.

expr: expr op=('*'|'/') expr # MulDiv
| expr op=('+'|'-') expr # AddSub
| INT # int
| ID # id
| '(' expr ')' # parens
;
  1. We need to define token names for the operator literals so we can reference token names as Java constants in the visitor
MUL:'*';
DIV:'/';

This time, we will use the visitor pattern and ANTLR will generate a method for each labeled alternative name

$ antlr4 -no-listener -visitor LabeledExpr.g4

It will also also generate default visitor implementation and we can subclass it. We will need to override methods associated with statement and expression alternatives.

Some interesting override is:

    @Override
    public Integer visitMulDiv(LabeledExprParser.MulDivContext ctx) {
        int left = visit(ctx.expr(0));  // get value of left subexpression
        int right = visit(ctx.expr(1)); // get value of right subexpression
        if ( ctx.op.getType() == LabeledExprParser.MUL ) return left * right;
        return left / right; // must be DIV
    }

Here, when we visit multi or divide, we will first infer the left and right expression. Then we will use ctx.op.getType to determine the type of the op. Then do operation accordingly.

Translation of java Source code

import java.util.List;
import java.util.Map;
public class Demo {
    void f(int x, String y) { }
    int[ ] g(/*no args*/) { return null; }
    List<Map<String, Integer>>[] h() { return null; }
}

We want to translate the source code into interface(just like header definition) while preserving whitespace and common.

<br />interface IDemo {
    void f(int x, String y);
    int[ ] g(/*no args*/);
    List<Map<String, Integer>>[] h();
}

We are given a Java Grammar and make a parse tree. We will derive interface from class name and grab signature(return type, name and arg list).

WE want to know how a class is decleared and how the method is defined.

classDeclaration
    :   'class' Identifier typeParameters? ('extends' type)?
        ('implements' typeList)?
        classBody
    ;
methodDeclaration
    :   type Identifier formalParameters ('[' ']')* methodDeclarationRest
    |   'void' Identifier formalParameters methodDeclarationRest
    ;

We will use antlr4 to get the visitors

$ antlr4 Java.g4

We do a

ls Java*.java 

and got

 JavaBaseListener.java JavaListener.java
 JavaLexer.java JavaParser.java

We will then extract an extended class from JavaBaseListener, (Java here means a listener for the Java grammar). We need to have 3 strategies:

  1. print out interface header at the start of a class
  2. print a terminating } at the end of class definition
  3. When we see each method definition, print out signature.
    @Override
    public void enterClassDeclaration(JavaParser.ClassDeclarationContext ctx){
        System.out.println("interface I"+ctx.Identifier()+" {");
    }

    @Override
    public void exitClassDeclaration(JavaParser.ClassDeclarationContext ctx) {
        System.out.println("}");
    }

    @Override
    public void enterMethodDeclaration(
        JavaParser.MethodDeclarationContext ctx
    )
    {
        // need parser to get tokens
        TokenStream tokens = parser.getTokenStream();
        String type = "void";
        if ( ctx.type()!=null ) {
            type = tokens.getText(ctx.type());
        }
        String args = tokens.getText(ctx.formalParameters());
        System.out.println("\t"+type+" "+ctx.Identifier()+args+";");
    }

We also need to write a main to run the parser and walk the tree with listener.

public class ExtractInterfaceTool {
    public static void main(String[] args) throws Exception {
        String inputFile = null;
        if ( args.length>0 ) inputFile = args[0];
        InputStream is = System.in;
        if ( inputFile!=null ) {
            is = new FileInputStream(inputFile);
        }
        ANTLRInputStream input = new ANTLRInputStream(is);

        JavaLexer lexer = new JavaLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        JavaParser parser = new JavaParser(tokens);
        ParseTree tree = parser.compilationUnit(); // parse

        ParseTreeWalker walker = new ParseTreeWalker(); // create standard walker
        ExtractInterfaceListener extractor = new ExtractInterfaceListener(parser);
        walker.walk(extractor, tree); // initiate walk of tree with listener
    }

embedding actions in a grammar

For more control, we can embed actions in grammar. These actions will be copied into the recursive-descent parser. actions are code snippets surrounded by curly braces.

Disclaimer :code snippets are from the ANTLR reference. If you found this note to be infrindging upon its copy right, please contact me and I will take it down.

Learning ANTLR 2: Some more example

In this post, I will go through a project that will recognize integers in curly braces such as {1,2,3} and {1,2,{3,4}}.

It might be useful in JAVA code refactoring that convert java array initialization. EG

static short[] data = {1,2,3};
to
static String data = "\u0001\u0002\u0003";

For more efficient initialization since JAVA do data[0] = 1, data[1] = 2 and data are not in compacted byte.

ANTLR structures

There are two main component: runtime and ANTLR tool

Tool

Runing ANTLR will generate parser and lexer that recognizes sentences described by the grammar.

Runtime

Runtime is a library of classes and methods needed by parser, lexer and token

Running ANTLR tool

After running the ANTLR tool on grammar.g4, we will get a bunch java files: If our grammar look like:

grammar ArrayInit;
/** A rule called init that matches comma-separated values between {...}. */
init : '{' value (',' value)* '}' ;
/** A value can be either a nested array/struct or a simple integer (INT) */
value : init | INT;

INT: [0-9] + ;
WS : [\t\r\n] + -> skip;

Generated files from ANTLR

ArrayParser.java

It will contain the parser that will recognize the array language syntax.

ArrayInit.tokens

Each token type will be assigned a token number and stored here.

ArrayInitListener.Java

A tree walk will fire “events” to a listener object that we provide.

Compile ANTLR code

javac *.java

If error, use this:

export CLASSPATH=".:/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH"

We use grun to run it and print out tokens crated by the lexer

grun ArrayInit init -tokens
{1,2,3}
ctlr-d

Perform actions based on parse tree

An application need to extract data from the parse tree to perform action. We will use call-back and react to input.

We will extend the base listener class and perform override enter and exit for method Init and Value

/** Convert short array inits like {1,2,3} to "\u0001\u0002\u0003" */
public class ShortToUnicodeString extends ArrayInitBaseListener {
    /** Translate { to " */
    @Override
    public void enterInit(ArrayInitParser.InitContext ctx) {
        System.out.print('"');
    }
    /** Translate } to " */
    @Override
        public void exitInit(ArrayInitParser.InitContext ctx) {
    System.out.print('"');
    }
    @Override
        public void enterValue(ArrayInitParser.ValueContext ctx) {
        // Assumes no nested array initializers
        int value = Integer.valueOf(ctx.INT().getText());
        System.out.printf("\\u%04x", value);
    }
}

When we enterValue, we will ask the context object for the INT token to find out the int value.

Then we will create a parse tree and parse it. Then use a walker to walk the tree. While walking the tree, it will trigger all enter and exit along the way.

ParseTreeWalker walker = new ParseTreeWalker();
// Walk the tree created during the parse, trigger callbacks
walker.walk(new ShortToUnicodeString(), tree);

The only thing we doodle with is the listener. It isolate the language application from the grammar.

LC94 Inorder Traversal of binary tree

Given a binary tree, return the inorder traversal of its nodes’ values.
In order traversal means visit the left, then the root, then the right.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        recurTraverse(root, res);
        return res;
    }
    void recurTraverse(TreeNode* root, vector<int>& res){
        if(root == NULL) return;
        recurTraverse(root -> left, res);
        res.push_back(root -> val);
        recurTraverse(root -> right, res);
    }
};

Iterative solution

In this code, we will use a stack to keep track of parent nodes.
We will first put root and all its left child node push onto the stack. And once we finished pushing all left child, we will pop the stack, store its value to res. Then if the poped node has right child, in the next iteration, we will push it and all its left child onto the stack. This method will ensure left-middle-right order.

    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> parentStack;
        vector<int> res;
        TreeNode* currNode = root;
        while(!parentStack.empty() || currNode){
            if(currNode){
                parentStack.push(currNode);
                currNode = currNode -> left;
            }
            else{
                TreeNode* tempNode = parentStack.top();
                parentStack.pop();
                res.push_back(tempNode -> val);
                currNode = tempNode -> right;
            }
        }
        return res;
    }

LC 93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: “25525511135” Output: [“255.255.11.135”, “255.255.111.35”]

An IP address has 4 parts. Each part will have a valid number in [0,255] Since each group can have 1, 2 or 3 numbers, we have 3x3x3x3 ways to splice the number.

BF

Just all 81 ways to splice the number and output all possible combination.

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        //use 4 nested for loop to generate all possible way 
        //to slice
        vector<string> res;
        for(int i = 1; i <= 3; i ++){
            for(int j = 1; j <= 3; j ++){
                for(int k = 1; k <= 3; k ++){
                    for(int l = 1; l <= 3; l ++){
                        if(i + j + k + l != s.size())
                            continue;
                        int i1 = stoi(s.substr(0, i));
                        int i2 = stoi(s.substr(i, j));
                        int i3 = stoi(s.substr(i + j, k));
                        int i4 = stoi(s.substr(i + j + k, l));
                        //cout<<i1 << " " << i2 <<" "<< i3<<" " << i4<< '\n';
                        if(i1 <= 255 && i2 <= 255 && i3 <= 255 && i4 <=255){
                            string ans = to_string(i1) + "." + to_string(i2) + "." + to_string(i3) + "." + to_string(i4);
                            //cout<<"ans is "<< ans<<endl;
                            if(ans.size() == s.size() + 3){
                                res.push_back(ans);
                                //cout<<ans<<endl;
                            }

                        }
                    }
                }
            }
        }//end of most outer forloop
        return res;
    }

};