Propositional Calculus Evaluation

Hi there, nothing new today, I've taken together, made it more usable and cleared a little bit some old code - parsing and evaluating of the logical expressions. I used an old tool: Reverse Polish Notation, where tokenizing, paring and evaluation are very simple. The whole file is about 195 lines of code. Unfortunately, the time complexity of the algorithm is exponential (in fact like any other algorithm for that, though the resolution method doing better for many types of formulas). How the tokenize, parse and eval functions works are described in greater details in many places, what I add is the fill_values function, which creates a whole table of logical values for the algorithm to check:

def fill_values(formula):
    """returns genexp with the all fillings with 0 and 1"""
    letters = "".join(set(re.findall("[A-Za-z]", formula)))
    for digits in product("10", repeat=len(letters)):
        table = str.maketrans(letters, "".join(digits))
        yield formula.translate(table)

It uses some Python features (that's why I like to use it, not for its efficiency, but because lots of libraries to quick get things done). The whole thing works something like that (asciinema screenacast):

https://asciinema.org/a/TarY4YQQTbm3To5ZpBXTci3Y4?t=8

Still lacks error handling, checks if a formula is syntactically correct. For example, it does this:

$ ./eval.py 
Propositional Logic Parser, press help, /h, -h or -usage for help
> q ~ a
Formula is satisfiable

I would like anybody doing some logic exercises, to try it out, or just for fun, that certainly will help:).

Code on Github . Out of the box here:
https://repl.it/@lion137/propositionalcalculluseval

 Thanks for patience, bye for now:)

Skew Heap In Java

Hello, just 've finished my Java implementation of a Skew Heap data structure and, also heap sort using this type of heap. It's very simple, under the hood structure is a binary tree, heap order is maintained via special merge function. Here is a basic structure:

public class SkewHeap <V extends Comparable<V>> {

    SkewNode root;
    public SkewHeap() {
        this.root = null;
    }

    class SkewNode {
        SkewNode leftChild, rightChild;
        V data;

        public SkewNode(V _data, SkewNode _left, SkewNode _right) {
            this.data = _data;
            this.leftChild = _left;
            this.rightChild = _right;
        }
    }
}

And here the crucial merge:

SkewNode merge(SkewNode left, SkewNode right) {
        if (null == left)
            return right;
        if (null == right)
            return left;
        if (left.data.compareTo(right.data) < 0 || left.data.compareTo(right.data) == 0) {
            return new SkewNode(left.data, merge(right, left.rightChild), left.leftChild);
        } else
            return new SkewNode(right.data, merge(left, right.rightChild), right.leftChild);
    }

It's doing exactly what's Wikipedia says: maintains structure and keeping minimum in the root. The others pop and insert use this procedure. Sorting is done via three functions:

SkewHeap listToHeap(List list) {
        SkewHeap o = new SkewHeap();
        for (int i = 0; i < list.size(); i++)
            o.insert((Comparable) list.get(i));
        return o;
    }

List heapToList(SkewHeap tree) {
        List ll = new ArrayList();
        try {
            while (true) {
                ll.add(tree.pop());
            }
        }
        catch (IndexOutOfBoundsException e) {
            return ll;
        }
    }

List sort(List list) {
        return heapToList(listToHeap(list));
    }

The first as is seen packs the list parameter to the heap, another stack the whole heap to the list (popping minimums), the resulted list must be sorted than, and finally the sort composes them two. Performance of sorting is O(nlog(n)), though is worse than standard Java sort. Code on github. Thank you.  
Sources: Wikipedia , What is Good About Haskell

Finding Fibonacci Numbers Using Lambda Calculus

Gues:t post in jupiter notebook:
Finding Fibonacci Numbers Using Lambda Calculus
Enjoy!

AVL Tree in Java

I have not blogged for some time, but there is something new:  AVL Tree in Java. Code on github: https://github.com/lion137/Java .
Thanks, enjoy! 

Fundamental Algorithms: Parse to RPN

Another one, Parsing to Reverse Polish Notation. Why it's so important? For example, typing to the first calculators, one had to do it in RPN! It's very easy to find a value of an expression in RPN. Deadly simple, having one, like:

3 2 + 4 3 * +

It's enough to take en empty LIFO stack, go through it and:
1 When we see a number push it on stack.
2. Seeing operand, pop stack twice, perform the operation and push result.
3. When done pop stack - this is result!

Parsing is not such easy, but is explained in details, for example, here.
Code on github.
Whole Series.

Thank you!

Fundamental Algorithms: Links

Links to whole series:
1. Order Statistics - C++
2. Polynomial GCD, Polynomial Division - Python
3. Recursive Permutations, All the Subset of Set and Variations With Repetitions - C++
4.Parsing (and evaluating) to RPN

Fundamental Algorithms III

Three more fundamental algorithms in the series. Today, recursive permutations, subsets of the given set and variations with repetitions. The all written in C++ (non generic, I used std::vector). Code (hope it's self explanatory, any questions ask). 
Whole series.
Thank you.