Interactive Programming Education Platform

Logic Practice

Introduction:

Ternary operators are extensively utilized in coding languages, offering a precise method for conveying conditional statements. Their distinct format can pose difficulties when analyzing them. This guide will delve into transforming ternary expressions into binary trees using a stack in C++. However, it is essential to first grasp the concept of ternary expressions in the context of 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 illustration, let's examine the subsequent ternary operation in C++:

✅ int result = (x is greater than 10) ? assign x to result : assign y to result;

If the x variable's value exceeds 10, the outcome will mirror the value of x itself. Conversely, if x fails to surpass 10 (meaning the x > 10 condition evaluates to false), the result will be set to the value of y.

Frequently, ternary expressions serve as convenient alternatives for basic conditional assignments or for embedding conditional logic within expressions, enhancing the code's clarity and readability. It is essential to exercise caution when utilizing them to prevent compromising code clarity or introducing unnecessary complexity.

Now, we are going to attempt the transformation of ternary expressions into binary trees through a C++ approach that relies on stacks. By leveraging fundamental data structures and established methodologies, these expressions can be transformed into a more organized format, which will simplify any future modifications or examinations.

Stack:

A stack represents a crucial data structure within the realm of computer science, operating based on the Last In First Out (LIFO) concept. This can be likened to a vertical arrangement of plates, allowing solely the addition (push) or removal (pop) of the uppermost 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 operators offer a concise and effective substitute for traditional if-else constructs. They provide a swift and straightforward way to handle conditions. While they excel in simplicity for basic scenarios, their clarity diminishes as the logic becomes more intricate. Additionally, managing intricate ternary expressions can pose challenges, especially during evaluation and optimization tasks.

Considering the expression a ? b : c, which denotes operands or sub-expressions in the tree. A structured alternative for conversion would involve transforming it into a binary tree format. This approach not only facilitates easier analysis and manipulations but also allows for straightforward traversal evaluation and potential optimization of the given expression.

To address this problem, we will develop a function that transforms ternary expressions into binary trees by leveraging a stack-driven approach in C++.

Utilizing the stack characteristics, this method is applied to efficiently build the tree by parsing the expression sequentially. By decomposing the expression into smaller units and arranging them hierarchically, we can generate a binary tree resembling the original ternary expression structure.

Program:

Example


#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Node structure for binary tree
struct TreeNode {
	char data;
	TreeNode *left, *right;
};

// Function to create a new node
TreeNode* createNewNode(char data) {
	TreeNode* node = new TreeNode;
	node->data = data;
	node->left = nullptr;
	node->right = nullptr;
	return node;
}

// Function to print the preorder traversal of the tree
void preorderTraversal(TreeNode* root) {
	if (root == nullptr)
		return;
	cout << root->data << " "; // Print current node
	preorderTraversal(root->left); // Traverse left subtree
	preorderTraversal(root->right); // Traverse right subtree
}

// Function to convert the expression to a binary tree
TreeNode* convertExpressionToBinaryTree(string expression) {
	stack<TreeNode*> stackNodes;

	// Iterate over the expression from end to start
	for (int i = expression.length() - 1; i >= 0;) {
		if ((i == expression.length() - 1)
			|| (i != 0 && ((expression[i - 1] == ':'
							&& expression[i + 1] == ':')
						|| (expression[i - 1] == '?'
							&& expression[i + 1] == ':')))) {
			// If the current character is the last character of the string
			// or it is preceded and succeeded by ':' or '?', respectively,
			// then push a new node containing the current character to the stack
			stackNodes.push(createNewNode(expression[i]));
		} else {
			// If the current character is not pushed directly to the stack,
			// then pop the top two nodes from the stack, as they represent
			// the left and right children of the current node
			// Create a new node for the current character and assign
			// the popped nodes as its left and right children
			TreeNode* leftNode = stackNodes.top();
			stackNodes.pop();
			TreeNode* rightNode = stackNodes.top();
			stackNodes.pop();
			TreeNode* currentNode = createNewNode(expression[i]);
			currentNode->left = leftNode;
			currentNode->right = rightNode;
			stackNodes.push(currentNode);
		}
		i -= 2; // Move to the previous operator or operand
	}

	// At the end, there will be only one element in the stack,
	// which will be the root of the binary tree
	return stackNodes.top();
}

// Driver code
int main() {
	string expression = "a?b:c";

	// Convert the expression to a binary tree
	TreeNode* root = convertExpressionToBinaryTree(expression);

	// Print the preorder traversal of the binary tree
	cout << "Preorder traversal of the constructed tree: ";
	preorderTraversal(root);

	return 0;
}

Output:

Output


Preorder traversal of the constructed tree: a b c

Explanation:

✅ Input Ternary Expression: In this example, the input expression is "a?b:c" which represents a ternary expression.
✅ 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.
✅ 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.
✅ 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.
✅ In this example, the input expression is "a?b:c" which represents a ternary expression.
✅ 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.
✅ 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.
✅ 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:

✅ 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.
✅ 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.
✅ 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.
✅ 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.
✅ 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.

Converting Ternary Expression To Binary Tree Using Stack In C++