Expression Trees

...

In prefix notation, the operator is placed before its operands. To construct an expression tree in prefix notation, we follow these steps:

1. Start from the leftmost part of the expression and read the tokens (operators and operands) from left to right.
2. If the current token is an operand, create a new node with the operand value and no children.
3. If the current token is an operator, create a new node with the operator value and assign the last two created nodes as its left and right children.
4. Push the newly created node onto a stack.
5. Repeat steps 2-4 until all tokens are processed.
6. The final node left on the stack is the root of the expression tree.

In postfix notation, the operator is placed after its operands. To construct an expression tree in postfix notation, we follow these steps:

1. Start from the leftmost part of the expression and read the tokens from left to right.
2. If the current token is an operand, create a new node with the operand value and no children.
3. If the current token is an operator, create a new node with the operator value, pop the last two created nodes from the stack, and assign them as its left and right children.
4. Push the newly created node onto the stack.
5. Repeat steps 2-4 until all tokens are processed.
6. The final node left on the stack is the root of the expression tree.

To convert an infix expression to postfix notation, we can use the shunting-yard algorithm. Here are the steps:

1. Initialize an empty stack and an empty output queue.
2. Read the infix expression from left to right.
3. If the current token is an operand, append it to the output queue.
4. If the current token is an operator, do the following:
   • While the stack is not empty and the top of the stack is an operator with higher precedence than the current token, pop operators from the stack and append them to the output queue.
   • Push the current token onto the stack.
5. If the current token is an opening parenthesis, push it onto the stack.
6. If the current token is a closing parenthesis, do the following:
   • Pop operators from the stack and append them to the output queue until an opening parenthesis is encountered (but do not append the opening parenthesis).
   • Pop the opening parenthesis from the stack.
7. Repeat steps 3-6 until all tokens are processed.
8. Pop any remaining operators from the stack and append them to the output queue.
9. The postfix expression is obtained by concatenating the tokens in the output queue.

To convert an infix expression to prefix notation, we can use a similar algorithm as infix to postfix conversion, but with a few modifications. Here are the steps:

1. Reverse the infix expression.
2. Replace opening parentheses with closing parentheses and vice versa.
3. Apply the infix to postfix conversion algorithm on the modified infix expression.
4. Reverse the resulting postfix expression to obtain the prefix expression.
   Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator). 
   Example :

Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2). 
Example :

Postfix :
Prefix :
Infix :
or
Postfix :
Prefix :
Infix :

def isOperator(x):

	if x in ["+", "-", "/", "*"]:
		return True
	else:
		return False

# Convert postfix to Prefix expression


def postToPre(post_exp):
	s = []
	# length of expression
	length = len(post_exp)

	# reading from right to left
	for i in range(length):
		# check if symbol is operator
		if (isOperator(post_exp[i])):
			# pop two operands from stack
			op1 = s[-1]
			s.pop()
			op2 = s[-1]
			s.pop()
			# concat the operands and operator
			temp = post_exp[i] + op2 + op1
			# Push string temp back to stack
			s.append(temp)
		# if symbol is an operand
		else:
			# push the operand to the stack
			s.append(post_exp[i])

	ans = ""
	for i in s:
		ans += i
	return ans

# Driver Code
if __name__ == "__main__":
	post_exp = "AB+CD-"
	# Function call
	print("Prefix : ", postToPre(post_exp))
Copy

# Example Input
s = "*-A/BC-/AKL"

# Stack for storing operands
stack = []

operators = set(['+', '-', '*', '/', '^'])

# Reversing the order
s = s[::-1]

# iterating through individual tokens
for i in s:

	# if token is operator
	if i in operators:

		# pop 2 elements from stack
		a = stack.pop()
		b = stack.pop()

		# concatenate them as operand1 +
		# operand2 + operator
		temp = a+b+i
		stack.append(temp)

	# else if operand
	else:
		stack.append(i)

# printing final output
print(*stack)
Copy

def prefix_to_infix(expression):
    stack = []
    operators = set(['+', '-', '*', '/', '^'])
    for i in range(len(expression)-1, -1, -1):
        if expression[i] in operators:
            op1 = stack.pop()
            op2 = stack.pop()
            stack.append('('+op1+expression[i]+op2+')')
        else:
            stack.append(expression[i])
    return stack.pop()
# Driver Code
if __name__ == "__main__":
	prefix = "*+AB-CD"
	# Function call
	print("infix : ", prefix_to_infix(prefix))
Copy

def infix_to_prefix(expression):
    stack = []
    operators = set(['+', '-', '*', '/', '^'])
    precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
    prefix = ''
    for i in range(len(expression)):
        if expression[i] == '(':
            stack.append('(')
        elif expression[i] == ')':
            while stack[-1] != '(':
                prefix += stack.pop()
            stack.pop()
        elif expression[i] not in operators:
            prefix += expression[i]
        else:
            while stack and stack[-1] != '(' and precedence[stack[-1]] >= precedence[expression[i]]:
                prefix += stack.pop()
            stack.append(expression[i])
    while stack:
        prefix += stack.pop()
    return prefix[::-1]
# Driver Code
if __name__ == "__main__":
	infix = "(A+B)*(C-D)"
	# Function call
	print("Prefix : ", infix_to_prefix(infix))
Copy

def postfix_to_infix(expression):
    stack = []
    operators = set(['+', '-', '*', '/', '^'])
    for i in range(len(expression)):
        if expression[i] in operators:
            op2 = stack.pop()
            op1 = stack.pop()
            stack.append('('+op1+expression[i]+op2+')')
        else:
            stack.append(expression[i])
    return stack.pop()
# Driver Code
if __name__ == "__main__":
	postfix = "AB+CD-*"
	# Function call
	print("infix : ", postfix_to_infix(postfix))
Copy

def infix_to_postfix(expression):
    stack = []
    output = ''
    operators = set(['+', '-', '*', '/', '^'])
    precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
    for i in range(len(expression)):
        if expression[i] == '(':
            stack.append('(')
        elif expression[i] == ')':
            while stack[-1] != '(':
                output += stack.pop()
            stack.pop()
        elif expression[i] not in operators:
            output += expression[i]
        else:
            while stack and stack[-1] != '(' and precedence[stack[-1]] >= precedence[expression[i]]:
                output += stack.pop()
            stack.append(expression[i])
    while stack:
        output += stack.pop()
    return output
# Driver Code
if __name__ == "__main__":
	infix = "(A+B)*(C-D)"
	# Function call
	print("postfix : ", infix_to_postfix(infix))
Copy

session 11