Converting ternary expression to Binary Tree using Stack in C++

Introduction:

Ternary expressions are widely used in programming languages, which provides us with a very clear way of expressing conditional statements. Their unique structure also gives challenges during analysis. In this article, we will discuss how to convert ternary expression to binary tree using stack in C++. But before discussing its implementation, we must know about the ternary expression in C++.

What is a Ternary Expression?

A ternary expression is generally called a conditional expression is a some kind of expression, of which a construct common to many programming languages thus:

• It is of the form (condition) ? (expression1) : (expression2).
• Here, the condition is evaluated to determine which of the two expressions will be used as a value.
• Condition is checked to evaluate either true or false, which specifies which of the two expressions will be used as a value.
• If the condition evaluates to true, the result of the ternary expression will be the value of expression1; otherwise, it will be the value of expression2.

As an example, let's consider the following ternary expression in C++:

• int result = (x > 10) ? x: y;

Let's see what happens in this expression:

• If the value of x is greater than 10, the result will be the value of x.
• If the value of x is not greater than 10 ( i.e., if the condition x > 10 becomes false), the result will be assigned the value y.

Many times, ternary expressions are used as shortcuts for simple conditional assignments or to include conditional logic within expressions, making the code clearer and more readable. However, they should be used carefully to avoid reducing code clarity or introducing complexity.

Now, we will try to convert ternary expressions into binary trees using a stack-based C++ method. Using the basic data structure and worked-out techniques, these expressions can be turned into something a little more structured -making them much easier for future manipulation or analysis.

Stack:

A stack is a fundamental data structure in computer science that follows the Last In First Out (LIFO) principle. It's similar to a stack of plates where we can only add (push) or remove (pop) the top plate.

These are the key operations that we can perform on a stack:

• Push: It adds an element to the top of the stack.
• Pop: It removes and returns the top element of the stack.
• Peek (or Top): It returns the top element of the stack without removing it.
• isEmpty: It checks if the stack is empty.
• Size: It returns the number of elements in the stack.

Problem Statement:

Ternary expressions are a compact but efficient alternative to if-else statements. Instead of using them, we can use these expressions easily and quickly. Although such expressions are easier when dealing with simple conditions, they may become complex and difficult to understand once the complexity grows too high. Moreover, processing raw ternary expressions can sometimes become difficult, particularly when we need to evaluate and optimise.

Consider the expression a ? b : c, which represents operands or sub-expressions in the tree. A more structured way to write conversion from this would be something like a binary tree - which makes analyses and manipulations easier as well. Representing the expression as a binary tree enables simpler traversal evaluation and probably optimization of the given.

To resolve this issue, we create a method that will convert ternary expressions to binary trees using a stack-based algorithm in C++.

With the stack properties, this approach is used to construct the tree efficiently while traversing the expression from left to right. We can create a binary tree that is similar to that of an original ternary expression by breaking down the expression into smaller components and organizing them into a hierarchical structure.

Program:

Output:

Preorder traversal of the constructed tree: a b c

Explanation:

1. Input Ternary Expression:
   • In this example, the input expression is "a?b:c" which represents a ternary expression.
2. Conversion to Binary Tree:
   • The function convertToBinaryTree iterates through each character of the expression we have given.
   • If the character is ?, it constructs a subtree with the top three nodes on the stack, where the condition is the root, the true expression is the left child, and the false expression is the right child.
   • If the character is an operand, it creates a node for it and pushes it onto the stack.
   • After processing all characters, the top node of the stack is the root of the binary tree.
3. Inorder Traversal:
   • The printTree function performs an inorder traversal of the binary tree.
   • It recursively traverses the left subtree, prints the value of the current node, and then recursively traverses the right subtree.
   • It prints the values of the nodes in sorted order.
4. Main Function:
   • In the main function, the input ternary expression is passed to convertToBinaryTree.
   • The resulting binary tree's inorder traversal is printed using printTree.

Time and Space Complexities:

Time Complexity:

• Traversal of the input expression will involve going through each character once and thus has a time complexity of O(n).
• Node creation for each operand/operator is constant time per node, which is O(n).
• Stack operations involve pushing and popping nodes. Each of them is done in constant time O(1).
• In the worst case, each character might require any stack operations, we have O(n) time complexity for the stack operations.
• Therefore, the time complexity of the conversion algorithm is O(n), and n- is the number of characters in the input ternary expression.

Space Complexity:

• The space complexity of an algorithm refers to the additional memory required for data structures.
• The primary space is consumed by the stack because it holds while converting.
• In the worst case, the stack can have all nodes of the binary tree, which gives O(n) space complexity. Each node created during the conversion process requires a constant amount of memory for node creation.
• The total number of nodes created will be proportional to the length of the input expression, which means O(n) space complexity for node creation.
• Therefore, the total space complexity will be O(n), where n is the length of the input ternary expression.

Uses of Converting Ternary Expression to Binary Tree:

1. Improved Readability: Ternary expressions are difficult to read. Converting them to a binary tree structure makes their representation clear, which provides better understanding by developers. It can improve the code's maintainability, help prevent bugs, and simply make the code easier to understand.
2. Facilitates Expression Evaluation: Binary trees provide a structured way to represent expressions, which can be easily evaluated through its standard algorithms, such as inorder, preorder, or postorder traversal. It is particularly useful for a dynamic evaluation of the ternary expression in the presence of different conditions.
3. Simplifies Optimization: Converting ternary expressions to binary trees can simplify more complex optimizations such as constant folding, common subexpression elimination, and code motion. Treating the expression in a structured binary tree form allows the exploitation of patterns and redundancies more easily, helping compilers to optimize the execution of code. Redundant subtrees may be identified and computed only once, reducing complex operations from being calculated.
4. Enables Transformation and Refactoring: Binary trees provide a rich structure for execution transformation and refactoring of ternary expressions. By manipulating the binary tree structure, rules can be used to apply various transformations. It includes algebraic simplifications, distribution of common terms, and special patterns like recognizing that one subtree exists on both sides of a commutative operation allowing refactoring.
5. Supports Compiler Optimizations: Several times, compiler optimizations depend on intermediate representations of code for analysis and transformation. Converting ternary expressions to binary trees provides a structured intermediate representation that compilers can analyze and optimize more effectively.