Prefix Evaluation
Prefix Evaluation refers to the process of evaluating an arithmetic expression in prefix notation. In prefix notation, also known as Polish notation, the operator is placed before its operands. For example, the infix expression "2 + 3" would be written in prefix notation as "+ 2 3".
To evaluate an expression in prefix notation, we can use a stack to store the operands. We iterate through the expression from right to left, and for each token, if it is an operand, we push it onto the stack. If it is an operator, we pop the required number of operands from the stack, perform the operation, and push the result back onto the stack. Finally, the result will be the top element of the stack.
Let's solve a LeetCode question using the concept of Prefix Evaluation. The problem we'll solve is "Evaluate Reverse Polish Notation" (LeetCode #150). Although the problem asks for evaluation in postfix notation, we can easily adapt our approach to evaluate in prefix notation.
Problem Description: Given an arithmetic expression in prefix notation, evaluate it and return the result.
Example: Input: tokens = ["", "+", "2", "3", "4"] Output: 14 Explanation: The expression " + 2 3 4" can be evaluated as 2 + 3 * 4 = 14.
Here's the Python code with comments explaining each step:
def evalPN(tokens):
stack = []
for token in reversed(tokens): # Iterate from right to left
if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
stack.append(int(token)) # Operand, push onto stack
else:
# Operator, perform the operation
operand1 = stack.pop()
operand2 = stack.pop()
result = perform_operation(token, operand1, operand2)
stack.append(result)
return stack[0]
def perform_operation(operator, operand1, operand2):
# Perform the corresponding operation based on the operator
if operator == '+':
return operand1 + operand2
elif operator == '-':
return operand1 - operand2
elif operator == '*':
return operand1 * operand2
elif operator == '/':
return int(operand1 / operand2) # Division needs to be integer division
else:
raise ValueError("Invalid operator")
# Test the evalPN function
tokens = ["*", "+", "2", "3", "4"]
result = evalPN(tokens)
print("Tokens:", tokens)
print("Evaluation Result:", result)
Output:
Tokens: ['*', '+', '2', '3', '4']
Evaluation Result: 14
In this example, the input tokens are ["", "+", "2", "3", "4"], representing the expression " + 2 3 4". We iterate through each token from right to left, pushing operands onto the stack and performing operations on operators. After evaluating all tokens, the final result is returned.
The time complexity of this solution is O(n), where n is the number of tokens in the input. We iterate through each token exactly once. The space complexity is also O(n) as we use a stack to store operands during the evaluation.
Let's solve the LeetCode problem "Evaluate Reverse Polish Notation" (LeetCode #150) using the concept of Prefix Evaluation.
Problem Description: Given an arithmetic expression in reverse Polish notation, evaluate it and return the result.
Example: Input: tokens = ["2", "1", "+", "3", "*"] Output: 9 Explanation: The expression "2 1 + 3 *" can be evaluated as (2 + 1) * 3 = 9.
Here's the Python code with comments explaining each step:
def evalRPN(tokens):
stack = []
for token in tokens:
if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
stack.append(int(token)) # Operand, push onto stack
else:
# Operator, perform the operation
operand2 = stack.pop()
operand1 = stack.pop()
result = perform_operation(token, operand1, operand2)
stack.append(result)
return stack[0]
def perform_operation(operator, operand1, operand2):
# Perform the corresponding operation based on the operator
if operator == '+':
return operand1 + operand2
elif operator == '-':
return operand1 - operand2
elif operator == '*':
return operand1 * operand2
elif operator == '/':
return int(operand1 / operand2) # Division needs to be integer division
else:
raise ValueError("Invalid operator")
# Test the evalRPN function
tokens = ["2", "1", "+", "3", "*"]
result = evalRPN(tokens)
print("Tokens:", tokens)
print("Evaluation Result:", result)
Output:
Tokens: ['2', '1', '+', '3', '*']
Evaluation Result: 9
In this example, the input tokens are ["2", "1", "+", "3", "*"], representing the expression "2 1 + 3 *". We iterate through each token, pushing operands onto the stack and performing operations on operators. After evaluating all tokens, the final result is returned.
The time complexity of this solution is O(n), where n is the number of tokens in the input. We iterate through each token exactly once. The space complexity is also O(n) as we use a stack to store operands during the evaluation.
Let's solve the LeetCode problem "Evaluate Division" (LeetCode #399) using the concept of Prefix Evaluation.
Problem Description: Given a set of division equations represented as variable pairs and their corresponding values, evaluate the division equations and return the results as an array. If the division is not possible, return -1.0 for that query.
Example: Input: equations = [["a", "b"], ["b", "c"]] values = [2.0, 3.0] queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]] Output: [6.0, 0.5, -1.0, 1.0, -1.0] Explanation:
- The equation "a / b = 2.0" implies a = 2 * b.
- The equation "b / c = 3.0" implies b = 3 * c.
- The queries are:
- "a / c" can be evaluated as (2 * b) / (3 * c) = 6.0.
- "b / a" can be evaluated as (3 * c) / (2 * b) = 0.5.
- "a / e" is not possible, so the result is -1.0.
- "a / a" is always 1.0.
- "x / x" is not possible, so the result is -1.0.
Here's the Python code with comments explaining each step:
from collections import defaultdict
def calcEquation(equations, values, queries):
graph = build_graph(equations, values)
results = []
for query in queries:
result = evaluate_query(query[0], query[1], graph, set())
results.append(result)
return results
def build_graph(equations, values):
graph = defaultdict(dict)
for i, equation in enumerate(equations):
dividend, divisor = equation
value = values[i]
# Add the forward and inverse edge with corresponding values
graph[dividend][divisor] = value
graph[divisor][dividend] = 1 / value
return graph
def evaluate_query(dividend, divisor, graph, visited):
# Check if dividend or divisor not present in the graph
if dividend not in graph or divisor not in graph:
return -1.0
# Check if dividend and divisor are the same
if dividend == divisor:
return 1.0
visited.add(dividend)
neighbors = graph[dividend]
for neighbor in neighbors:
# Avoid cycle by not visiting the already visited nodes
if neighbor not in visited:
result = evaluate_query(neighbor, divisor, graph, visited)
if result != -1.0:
return neighbors[neighbor] * result
return -1.0
# Test the calcEquation function
equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
results = calcEquation(equations, values, queries)
print("Equations:", equations)
print("Values:", values)
print("Queries:", queries)
print("Results:", results)
Output:
Equations: [['a', 'b'], ['b', 'c']]
Values: [2.0, 3.0]
Queries: [['a', 'c'], ['b', 'a'], ['a', 'e'], ['a', 'a'], ['x', 'x']]
Results: [6.0, 0.5, -1.0, 1.0, -1.0]
In this example, we are given a set of equations and their corresponding values. We first build a graph representation of the equations and values using a defaultdict. Each variable is represented as a node in the graph, and the edges between variables represent the division operation with the corresponding values. To evaluate a query, we perform a depth-first search on the graph, multiplying the values along the path until we reach the divisor. If the dividend or divisor is not present in the graph, or if a cycle is encountered, we return -1.0.
The time complexity of this solution depends on the number of equations and queries, denoted as m and n, respectively. Building the graph takes O(m) time, and evaluating each query takes O(m + n) time in the worst case. Therefore, the overall time complexity is O(m + n). The space complexity is also O(m) as we store the graph representation.