Given this BNF-style grammar write a Python function `evaluate(str)` that evaluates the expression <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> <prefix-op> ::= 'sin' | 'cos' <number> ::= <digit> | <number> <digit> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' For example you can evaluate this sin(3 + 2 * 4) - cos(15) = -0.240302
Given this BNF-style grammar write a Python function `evaluate(str)` that evaluates the expression <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> <prefix-op> ::= 'sin' | 'cos' <number> ::= <digit> | <number> <digit> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' For example you can evaluate this sin(3 + 2 * 4) - cos(15) = -0.240302
# Recursive Descent Parser for Arithmetic Expressions I'll implement a recursive descent parser that follows the grammar you provided. This approach creates functions that directly correspond to each rule in the grammar.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | import math def evaluate(s): # Remove whitespace from the input string s = s.replace(' ', '') # Use a list to track position so it can be modified in nested functions pos = [0] # Parse an expression: <term> | <expression> '+' <term> | <expression> '-' <term> def parse_expression(): left = parse_term() while pos[0] < len(s) and s[pos[0]] in ['+', '-']: op = s[pos[0]] pos[0] += 1 right = parse_term() if op == '+': left += right else: # op == '-' left -= right return left # Parse a term: <factor> | <term> '*' <factor> | <term> '/' <factor> def parse_term(): left = parse_factor() while pos[0] < len(s) and s[pos[0]] in ['*', '/']: op = s[pos[0]] pos[0] += 1 right = parse_factor() if op == '*': left *= right else: # op == '/' left /= right return left # Parse a factor: <number> | '(' <expression> ')' | <prefix-op> <factor> def parse_factor(): if pos[0] < len(s) and s[pos[0]].isdigit(): return parse_number() elif pos[0] < len(s) and s[pos[0]] == '(': pos[0] += 1 # Skip '(' result = parse_expression() if pos[0] >= len(s) or s[pos[0]] != ')': raise ValueError("Expected closing parenthesis") pos[0] += 1 # Skip ')' return result elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 # Skip 'sin' return math.sin(parse_factor()) elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 # Skip 'cos' return math.cos(parse_factor()) else: raise ValueError(f"Unexpected character at position {pos[0]}") # Parse a number: <digit> | <number> <digit> def parse_number(): start = pos[0] while pos[0] < len(s) and s[pos[0]].isdigit(): pos[0] += 1 return int(s[start:pos[0]]) # Start parsing from the beginning result = parse_expression() # Ensure the entire string was parsed if pos[0] < len(s): raise ValueError(f"Unexpected character at position {pos[0]}: {s[pos[0]]}") return result |
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | import math def evaluate(s): # Remove whitespace from the input string s = s.replace(' ', '') # Use a list to track position so it can be modified in nested functions pos = [0] # Parse an expression: <term> | <expression> '+' <term> | <expression> '-' <term> def parse_expression(): left = parse_term() while pos[0] < len(s) and s[pos[0]] in ['+', '-']: op = s[pos[0]] pos[0] += 1 right = parse_term() if op == '+': left += right else: # op == '-' left -= right return left # Parse a term: <factor> | <term> '*' <factor> | <term> '/' <factor> def parse_term(): left = parse_factor() while pos[0] < len(s) and s[pos[0]] in ['*', '/']: op = s[pos[0]] pos[0] += 1 right = parse_factor() if op == '*': left *= right else: # op == '/' left /= right return left # Parse a factor: <number> | '(' <expression> ')' | <prefix-op> <factor> def parse_factor(): if pos[0] < len(s) and s[pos[0]].isdigit(): return parse_number() elif pos[0] < len(s) and s[pos[0]] == '(': pos[0] += 1 # Skip '(' result = parse_expression() if pos[0] >= len(s) or s[pos[0]] != ')': raise ValueError("Expected closing parenthesis") pos[0] += 1 # Skip ')' return result elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 # Skip 'sin' return math.sin(parse_factor()) elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 # Skip 'cos' return math.cos(parse_factor()) else: raise ValueError(f"Unexpected character at position {pos[0]}") # Parse a number: <digit> | <number> <digit> def parse_number(): start = pos[0] while pos[0] < len(s) and s[pos[0]].isdigit(): pos[0] += 1 return int(s[start:pos[0]]) # Start parsing from the beginning result = parse_expression() # Ensure the entire string was parsed if pos[0] < len(s): raise ValueError(f"Unexpected character at position {pos[0]}: {s[pos[0]]}") return result |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | import math def evaluate(s): # Remove whitespace from the input string s = s.replace(' ', '') # Use a list to track position so it can be modified in nested functions pos = [0] # Parse an expression: <term> | <expression> '+' <term> | <expression> '-' <term> def parse_expression(): left = parse_term() while pos[0] < len(s) and s[pos[0]] in ['+', '-']: op = s[pos[0]] pos[0] += 1 right = parse_term() if op == '+': left += right else: # op == '-' left -= right return left # Parse a term: <factor> | <term> '*' <factor> | <term> '/' <factor> def parse_term(): left = parse_factor() while pos[0] < len(s) and s[pos[0]] in ['*', '/']: op = s[pos[0]] pos[0] += 1 right = parse_factor() if op == '*': left *= right else: # op == '/' left /= right return left # Parse a factor: <number> | '(' <expression> ')' | <prefix-op> <factor> def parse_factor(): if pos[0] < len(s) and s[pos[0]].isdigit(): return parse_number() elif pos[0] < len(s) and s[pos[0]] == '(': pos[0] += 1 # Skip '(' result = parse_expression() if pos[0] >= len(s) or s[pos[0]] != ')': raise ValueError("Expected closing parenthesis") pos[0] += 1 # Skip ')' return result elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 # Skip 'sin' return math.sin(parse_factor()) elif pos[0] + 3 <= len(s) and s[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 # Skip 'cos' return math.cos(parse_factor()) else: raise ValueError(f"Unexpected character at position {pos[0]}") # Parse a number: <digit> | <number> <digit> def parse_number(): start = pos[0] while pos[0] < len(s) and s[pos[0]].isdigit(): pos[0] += 1 return int(s[start:pos[0]]) # Start parsing from the beginning result = parse_expression() # Ensure the entire string was parsed if pos[0] < len(s): raise ValueError(f"Unexpected character at position {pos[0]}: {s[pos[0]]}") return result answer = round(evaluate('sin(35+2*4)-cos(15)'), 5) expected = -0.07209 assert answer == expected, f'Wrong answer; got {answer} instead of {expected}' print('All tests passed') |
All tests passed
Testing if the previous output contains the string All tests passed
: True
Given this BNF-style grammar write a Python function `evaluate(str)` that evaluates the expression <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> <prefix-op> ::= 'sin' | 'cos' <number> ::= <digit> | <number> <digit> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' For example you can evaluate this sin(3 + 2 * 4) - cos(15) = -0.240302
Given this BNF-style grammar write a Python function `evaluate(str)` that evaluates the expression <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> <prefix-op> ::= 'sin' | 'cos' <number> ::= <digit> | <number> <digit> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' For example you can evaluate this sin(3 + 2 * 4) - cos(15) = -0.240302
# Expression Evaluator using Recursive Descent Parsing Below is a Python implementation of an expression evaluator that follows the given BNF grammar. This solution uses recursive descent parsing, which matches the structure of the grammar nicely.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | import math def evaluate(expression_str): """ Evaluates a mathematical expression based on the specified grammar. Args: expression_str: A string containing the expression to evaluate Returns: The numeric result of evaluating the expression """ # Remove whitespace expression_str = expression_str.replace(" ", "") # Initialize the parsing position pos = [0] # Using a list so it can be modified within nested function calls # Parse and evaluate the expression result = parse_expression(expression_str, pos) # Check if we consumed the entire input if pos[0] < len(expression_str): raise ValueError(f"Unexpected character '{expression_str[pos[0]]}' at position {pos[0]}") return result def parse_expression(expr, pos): """Parse expressions following the rule: <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>""" left = parse_term(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '+': pos[0] += 1 right = parse_term(expr, pos) left += right elif expr[pos[0]] == '-': pos[0] += 1 right = parse_term(expr, pos) left -= right else: break return left def parse_term(expr, pos): """Parse terms following the rule: <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor>""" left = parse_factor(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '*': pos[0] += 1 right = parse_factor(expr, pos) left *= right elif expr[pos[0]] == '/': pos[0] += 1 right = parse_factor(expr, pos) left /= right else: break return left def parse_factor(expr, pos): """Parse factors following the rule: <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor>""" if pos[0] >= len(expr): raise ValueError("Unexpected end of expression") # Check for prefix operators (sin, cos) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.sin(factor_value) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.cos(factor_value) # Check for parenthesized expression if expr[pos[0]] == '(': pos[0] += 1 result = parse_expression(expr, pos) if pos[0] >= len(expr) or expr[pos[0]] != ')': raise ValueError("Missing closing parenthesis") pos[0] += 1 return result # Must be a number return parse_number(expr, pos) def parse_number(expr, pos): """Parse a number following the rules: <number> ::= <digit> | <number> <digit>""" start = pos[0] while pos[0] < len(expr) and expr[pos[0]].isdigit(): pos[0] += 1 if start == pos[0]: raise ValueError(f"Expected a number at position {pos[0]}") return int(expr[start:pos[0]]) |
1 2 3 | # Test with the given example result = evaluate("sin(3 + 2 * 4) - cos(15)") print(result) # Should output approximately -0.240302 |
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | import math def evaluate(expression_str): """ Evaluates a mathematical expression based on the specified grammar. Args: expression_str: A string containing the expression to evaluate Returns: The numeric result of evaluating the expression """ # Remove whitespace expression_str = expression_str.replace(" ", "") # Initialize the parsing position pos = [0] # Using a list so it can be modified within nested function calls # Parse and evaluate the expression result = parse_expression(expression_str, pos) # Check if we consumed the entire input if pos[0] < len(expression_str): raise ValueError(f"Unexpected character '{expression_str[pos[0]]}' at position {pos[0]}") return result def parse_expression(expr, pos): """Parse expressions following the rule: <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>""" left = parse_term(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '+': pos[0] += 1 right = parse_term(expr, pos) left += right elif expr[pos[0]] == '-': pos[0] += 1 right = parse_term(expr, pos) left -= right else: break return left def parse_term(expr, pos): """Parse terms following the rule: <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor>""" left = parse_factor(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '*': pos[0] += 1 right = parse_factor(expr, pos) left *= right elif expr[pos[0]] == '/': pos[0] += 1 right = parse_factor(expr, pos) left /= right else: break return left def parse_factor(expr, pos): """Parse factors following the rule: <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor>""" if pos[0] >= len(expr): raise ValueError("Unexpected end of expression") # Check for prefix operators (sin, cos) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.sin(factor_value) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.cos(factor_value) # Check for parenthesized expression if expr[pos[0]] == '(': pos[0] += 1 result = parse_expression(expr, pos) if pos[0] >= len(expr) or expr[pos[0]] != ')': raise ValueError("Missing closing parenthesis") pos[0] += 1 return result # Must be a number return parse_number(expr, pos) def parse_number(expr, pos): """Parse a number following the rules: <number> ::= <digit> | <number> <digit>""" start = pos[0] while pos[0] < len(expr) and expr[pos[0]].isdigit(): pos[0] += 1 if start == pos[0]: raise ValueError(f"Expected a number at position {pos[0]}") return int(expr[start:pos[0]]) |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | import math def evaluate(expression_str): """ Evaluates a mathematical expression based on the specified grammar. Args: expression_str: A string containing the expression to evaluate Returns: The numeric result of evaluating the expression """ # Remove whitespace expression_str = expression_str.replace(" ", "") # Initialize the parsing position pos = [0] # Using a list so it can be modified within nested function calls # Parse and evaluate the expression result = parse_expression(expression_str, pos) # Check if we consumed the entire input if pos[0] < len(expression_str): raise ValueError(f"Unexpected character '{expression_str[pos[0]]}' at position {pos[0]}") return result def parse_expression(expr, pos): """Parse expressions following the rule: <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>""" left = parse_term(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '+': pos[0] += 1 right = parse_term(expr, pos) left += right elif expr[pos[0]] == '-': pos[0] += 1 right = parse_term(expr, pos) left -= right else: break return left def parse_term(expr, pos): """Parse terms following the rule: <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor>""" left = parse_factor(expr, pos) while pos[0] < len(expr): if expr[pos[0]] == '*': pos[0] += 1 right = parse_factor(expr, pos) left *= right elif expr[pos[0]] == '/': pos[0] += 1 right = parse_factor(expr, pos) left /= right else: break return left def parse_factor(expr, pos): """Parse factors following the rule: <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor>""" if pos[0] >= len(expr): raise ValueError("Unexpected end of expression") # Check for prefix operators (sin, cos) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'sin': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.sin(factor_value) if pos[0] + 3 <= len(expr) and expr[pos[0]:pos[0]+3] == 'cos': pos[0] += 3 factor_value = parse_factor(expr, pos) return math.cos(factor_value) # Check for parenthesized expression if expr[pos[0]] == '(': pos[0] += 1 result = parse_expression(expr, pos) if pos[0] >= len(expr) or expr[pos[0]] != ')': raise ValueError("Missing closing parenthesis") pos[0] += 1 return result # Must be a number return parse_number(expr, pos) def parse_number(expr, pos): """Parse a number following the rules: <number> ::= <digit> | <number> <digit>""" start = pos[0] while pos[0] < len(expr) and expr[pos[0]].isdigit(): pos[0] += 1 if start == pos[0]: raise ValueError(f"Expected a number at position {pos[0]}") return int(expr[start:pos[0]]) answer = round(evaluate('sin(35+2*4)-cos(15)'), 5) expected = -0.07209 assert answer == expected, f'Wrong answer; got {answer} instead of {expected}' print('All tests passed') |
All tests passed
Testing if the previous output contains the string All tests passed
: True