Task-1
Output
The code takes a string, which is a propositional logic in Infix form, and outputs a string, which
is in form of postfix form of the given input.
Efficiency-
The time complexity of the algorithm is O(N), where N is the length of the input string. The Boolean
functions used in the code to check symbols and bracket run in O(1) complexity, and the task1
function runs in O(N) complexity, as it contains some for and while loops which occur one after the
other.
Memory-
The space complexity of our algorithm is O(N). The function task1 duplicates the string 3 times, and
also uses a stack. This makes our overall space usage 4N, where N is the size of string.
Task-2
Output
The code horizontally displays the parse tree in form of a string in the terminal. The input string
is prefix propositional logic expression. This is converted to a parse tree and then displayed in
form of a string.
Efficiency-
The time complexity of the algorithm is O(N). The buildParseTree function traverses the string of
size N once, and so does the displayTree function. The displayTree function traverses the tree once
recursively, in order to print it. All the other functions run in O(1) complexity.
Memory-
The space complexity of our algorithm is O(N). This is because, N nodes of tree are stored in
memory.
Task-3
Output
The code returns infix form of the input parse tree, in string format. The code takes input tree in
form of a string, converts it to a binary tree. After this, it traverses the tree recursively to
return the infix form of the parse tree.
Efficiency-
The time complexity of the algorithm is O(N). The buildParseTree function traverses the string of
size N once, and so does the displayTree function. The inOrderTraversal function traverses the tree
recursively once. This takes complexity of O(N), where N is the number of nodes.
Memory-
The space complexity of our algorithm is O(N). This is because, N characters of the input string are
converted to nodes of the tree. These N nodes are stored in the memory.
Task-4
Output
The code prints the height of the input parse tree in form of integer. It takes tree as an input,
and then calculates the height using heightRecursive function, and returns the height in integer
format.
Efficiency-
The time complexity of the algorithm is O(N). The heightRecursive function recursively traverses all
the nodes (N) in order to calculate the height of the tree. Also, the code traverses the input
string of size N to generate a tree.
Memory-
The space complexity of our algorithm is O(N). This is because, N nodes are stored in form of a
tree.
Task-5
Output
The code returns the Boolean value of input propositional logic formula. First, we input the
propositional logic formula in form of string, then the code converts it to parse tree form. Then,
it calculates the output using the parse tree.
Efficiency-
The time complexity of the algorithm is O(N). In the input string with N characters, the code
converts it to parse tree with N nodes. Also, getTruthValue function traverses the N nodes in order
to calculate the truth value of the propositional formula.
Memory-
The space complexity of our algorithm is O(N). This is because, N nodes are stored in form of a
tree. Also, we use map to store the truth value of each atom, and a set to store the checked atom.