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
Certainly! Below is a Python implementation of the `evaluate` function based on the provided BNF-style grammar. This function uses a recursive descent parser approach to parse and evaluate arithmetic expressions, including handling of `sin` and `cos` prefix operations.
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 | import math class Tokenizer: def __init__(self, s): self.tokens = self.tokenize(s) self.pos = 0 def tokenize(self, s): tokens = [] i = 0 while i < len(s): if s[i].isspace(): i += 1 elif s[i].isdigit(): num = s[i] i += 1 while i < len(s) and s[i].isdigit(): num += s[i] i += 1 tokens.append(num) elif s[i].isalpha(): ident = s[i] i += 1 while i < len(s) and s[i].isalpha(): ident += s[i] i += 1 tokens.append(ident) elif s[i] in '+-*/()': tokens.append(s[i]) i += 1 else: raise ValueError(f"Unknown character: {s[i]}") return tokens def peek(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return None def next(self): tok = self.peek() if tok is not None: self.pos += 1 return tok def evaluate(s): tokenizer = Tokenizer(s) def parse_expression(): value = parse_term() while True: tok = tokenizer.peek() if tok == '+': tokenizer.next() value += parse_term() elif tok == '-': tokenizer.next() value -= parse_term() else: break return value def parse_term(): value = parse_factor() while True: tok = tokenizer.peek() if tok == '*': tokenizer.next() value *= parse_factor() elif tok == '/': tokenizer.next() denominator = parse_factor() value /= denominator else: break return value def parse_factor(): tok = tokenizer.peek() if tok in ('sin', 'cos'): tokenizer.next() val = parse_factor() if tok == 'sin': return math.sin(val) else: return math.cos(val) elif tok == '(': tokenizer.next() val = parse_expression() if tokenizer.next() != ')': raise ValueError("Expected ')'") return val elif tok is not None and tok.isdigit(): tokenizer.next() return float(tok) else: raise ValueError(f"Unexpected token: {tok}") result = parse_expression() if tokenizer.peek() is not None: raise ValueError("Unexpected input after expression") return result # Example usage: if __name__ == "__main__": expr = "sin(3 + 2 * 4) - cos(15)" result = evaluate(expr) print(f"{expr} = {result:.6f}") # Output: sin(3 + 2 * 4) - cos(15) = -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 105 106 107 108 | import math class Tokenizer: def __init__(self, s): self.tokens = self.tokenize(s) self.pos = 0 def tokenize(self, s): tokens = [] i = 0 while i < len(s): if s[i].isspace(): i += 1 elif s[i].isdigit(): num = s[i] i += 1 while i < len(s) and s[i].isdigit(): num += s[i] i += 1 tokens.append(num) elif s[i].isalpha(): ident = s[i] i += 1 while i < len(s) and s[i].isalpha(): ident += s[i] i += 1 tokens.append(ident) elif s[i] in '+-*/()': tokens.append(s[i]) i += 1 else: raise ValueError(f"Unknown character: {s[i]}") return tokens def peek(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return None def next(self): tok = self.peek() if tok is not None: self.pos += 1 return tok def evaluate(s): tokenizer = Tokenizer(s) def parse_expression(): value = parse_term() while True: tok = tokenizer.peek() if tok == '+': tokenizer.next() value += parse_term() elif tok == '-': tokenizer.next() value -= parse_term() else: break return value def parse_term(): value = parse_factor() while True: tok = tokenizer.peek() if tok == '*': tokenizer.next() value *= parse_factor() elif tok == '/': tokenizer.next() denominator = parse_factor() value /= denominator else: break return value def parse_factor(): tok = tokenizer.peek() if tok in ('sin', 'cos'): tokenizer.next() val = parse_factor() if tok == 'sin': return math.sin(val) else: return math.cos(val) elif tok == '(': tokenizer.next() val = parse_expression() if tokenizer.next() != ')': raise ValueError("Expected ')'") return val elif tok is not None and tok.isdigit(): tokenizer.next() return float(tok) else: raise ValueError(f"Unexpected token: {tok}") result = parse_expression() if tokenizer.peek() is not None: raise ValueError("Unexpected input after expression") return result # Example usage: if __name__ == "__main__": expr = "sin(3 + 2 * 4) - cos(15)" result = evaluate(expr) print(f"{expr} = {result:.6f}") # Output: sin(3 + 2 * 4) - cos(15) = -0.240302 |
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 114 115 116 117 | import math class Tokenizer: def __init__(self, s): self.tokens = self.tokenize(s) self.pos = 0 def tokenize(self, s): tokens = [] i = 0 while i < len(s): if s[i].isspace(): i += 1 elif s[i].isdigit(): num = s[i] i += 1 while i < len(s) and s[i].isdigit(): num += s[i] i += 1 tokens.append(num) elif s[i].isalpha(): ident = s[i] i += 1 while i < len(s) and s[i].isalpha(): ident += s[i] i += 1 tokens.append(ident) elif s[i] in '+-*/()': tokens.append(s[i]) i += 1 else: raise ValueError(f"Unknown character: {s[i]}") return tokens def peek(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return None def next(self): tok = self.peek() if tok is not None: self.pos += 1 return tok def evaluate(s): tokenizer = Tokenizer(s) def parse_expression(): value = parse_term() while True: tok = tokenizer.peek() if tok == '+': tokenizer.next() value += parse_term() elif tok == '-': tokenizer.next() value -= parse_term() else: break return value def parse_term(): value = parse_factor() while True: tok = tokenizer.peek() if tok == '*': tokenizer.next() value *= parse_factor() elif tok == '/': tokenizer.next() denominator = parse_factor() value /= denominator else: break return value def parse_factor(): tok = tokenizer.peek() if tok in ('sin', 'cos'): tokenizer.next() val = parse_factor() if tok == 'sin': return math.sin(val) else: return math.cos(val) elif tok == '(': tokenizer.next() val = parse_expression() if tokenizer.next() != ')': raise ValueError("Expected ')'") return val elif tok is not None and tok.isdigit(): tokenizer.next() return float(tok) else: raise ValueError(f"Unexpected token: {tok}") result = parse_expression() if tokenizer.peek() is not None: raise ValueError("Unexpected input after expression") return result # Example usage: if __name__ == "__main__": expr = "sin(3 + 2 * 4) - cos(15)" result = evaluate(expr) print(f"{expr} = {result:.6f}") # Output: sin(3 + 2 * 4) - cos(15) = -0.240302 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') |
sin(3 + 2 * 4) - cos(15) = -0.240302
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
Certainly! Below is a Python function `evaluate` that parses and evaluates arithmetic expressions based on the provided BNF grammar. This implementation uses a **recursive descent parser** to handle the grammar's rules, ensuring correct operator precedence and support for the `sin` and `cos` prefix operators. ### Key Features: - **Tokenizer**: Converts the input string into a list of tokens, handling numbers, operators, parentheses, and function names (`sin`, `cos`). - **Parser**: Implements recursive methods to parse expressions, terms, and factors according to the grammar. - **Evaluation**: Computes the expression's value using Python's `math` library for trigonometric functions, assuming inputs are in radians. ### Implementation:
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 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | import math def evaluate(expression): """ Evaluates an arithmetic expression with support for +, -, *, /, parentheses, and prefix operators 'sin' and 'cos'. Assumes that functions take arguments in radians. Example: evaluate("sin(3 + 2 * 4) - cos(15)") # Returns approximately -0.240302 """ def tokenize(expr): """ Converts the input string into a list of tokens. Tokens can be numbers, operators, parentheses, or function names. """ tokens = [] i = 0 while i < len(expr): if expr[i].isspace(): i += 1 continue elif expr[i].isdigit(): num = expr[i] i += 1 while i < len(expr) and expr[i].isdigit(): num += expr[i] i += 1 tokens.append(num) elif expr[i].isalpha(): ident = expr[i] i += 1 while i < len(expr) and expr[i].isalpha(): ident += expr[i] i += 1 if ident in ('sin', 'cos'): tokens.append(ident) else: raise ValueError(f"Unknown identifier: {ident}") elif expr[i] in '+-*/()': tokens.append(expr[i]) i += 1 else: raise ValueError(f"Unknown character: {expr[i]}") return tokens class Parser: """ Implements a recursive descent parser based on the provided BNF grammar. """ def __init__(self, tokens): self.tokens = tokens self.pos = 0 def is_end(self): return self.pos >= len(self.tokens) def current_token(self): if self.is_end(): return None return self.tokens[self.pos] def consume(self, expected=None): tok = self.current_token() if expected and tok != expected: raise ValueError(f"Expected '{expected}', got '{tok}'") self.pos += 1 return tok def parse_expression(self): """ Parses <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> """ value = self.parse_term() while not self.is_end() and self.current_token() in ('+', '-'): op = self.consume() term = self.parse_term() if op == '+': value += term else: value -= term return value def parse_term(self): """ Parses <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> """ value = self.parse_factor() while not self.is_end() and self.current_token() in ('*', '/'): op = self.consume() factor = self.parse_factor() if op == '*': value *= factor else: if factor == 0: raise ZeroDivisionError("Division by zero") value /= factor return value def parse_factor(self): """ Parses <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> """ tok = self.current_token() if tok in ('sin', 'cos'): op = self.consume() factor = self.parse_factor() if op == 'sin': return math.sin(factor) else: return math.cos(factor) elif tok == '(': self.consume('(') value = self.parse_expression() self.consume(')') return value else: return self.parse_number() def parse_number(self): """ Parses <number> ::= <digit> | <number> <digit> """ tok = self.consume() if not tok.isdigit(): raise ValueError(f"Expected number, got '{tok}'") return float(tok) # Tokenize the input expression tokens = tokenize(expression) # Create a parser instance with the tokens parser = Parser(tokens) # Parse and evaluate the expression result = parser.parse_expression() # Ensure all tokens have been consumed if not parser.is_end(): raise ValueError("Unexpected tokens at the end of the expression") return result # Example usage: if __name__ == "__main__": expr = "sin(3 + 2 * 4) - cos(15)" result = evaluate(expr) print(f"{expr} = {result:.6f}") # Outputs: sin(3 + 2 * 4) - cos(15) = -0.240302 |
1 2 3 | expr = "sin(3 + 2 * 4) - cos(15)" result = evaluate(expr) print(f"{expr} = {result:.6f}") # Outputs: sin(3 + 2 * 4) - cos(15) = -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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | import math def evaluate(expression): """ Evaluates an arithmetic expression with support for +, -, *, /, parentheses, and prefix operators 'sin' and 'cos'. Assumes that functions take arguments in radians. Example: evaluate("sin(3 + 2 * 4) - cos(15)") # Returns approximately -0.240302 """ def tokenize(expr): """ Converts the input string into a list of tokens. Tokens can be numbers, operators, parentheses, or function names. """ tokens = [] i = 0 while i < len(expr): if expr[i].isspace(): i += 1 continue elif expr[i].isdigit(): num = expr[i] i += 1 while i < len(expr) and expr[i].isdigit(): num += expr[i] i += 1 tokens.append(num) elif expr[i].isalpha(): ident = expr[i] i += 1 while i < len(expr) and expr[i].isalpha(): ident += expr[i] i += 1 if ident in ('sin', 'cos'): tokens.append(ident) else: raise ValueError(f"Unknown identifier: {ident}") elif expr[i] in '+-*/()': tokens.append(expr[i]) i += 1 else: raise ValueError(f"Unknown character: {expr[i]}") return tokens class Parser: """ Implements a recursive descent parser based on the provided BNF grammar. """ def __init__(self, tokens): self.tokens = tokens self.pos = 0 def is_end(self): return self.pos >= len(self.tokens) def current_token(self): if self.is_end(): return None return self.tokens[self.pos] def consume(self, expected=None): tok = self.current_token() if expected and tok != expected: raise ValueError(f"Expected '{expected}', got '{tok}'") self.pos += 1 return tok def parse_expression(self): """ Parses <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> """ value = self.parse_term() while not self.is_end() and self.current_token() in ('+', '-'): op = self.consume() term = self.parse_term() if op == '+': value += term else: value -= term return value def parse_term(self): """ Parses <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> """ value = self.parse_factor() while not self.is_end() and self.current_token() in ('*', '/'): op = self.consume() factor = self.parse_factor() if op == '*': value *= factor else: if factor == 0: raise ZeroDivisionError("Division by zero") value /= factor return value def parse_factor(self): """ Parses <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> """ tok = self.current_token() if tok in ('sin', 'cos'): op = self.consume() factor = self.parse_factor() if op == 'sin': return math.sin(factor) else: return math.cos(factor) elif tok == '(': self.consume('(') value = self.parse_expression() self.consume(')') return value else: return self.parse_number() def parse_number(self): """ Parses <number> ::= <digit> | <number> <digit> """ tok = self.consume() if not tok.isdigit(): raise ValueError(f"Expected number, got '{tok}'") return float(tok) # Tokenize the input expression tokens = tokenize(expression) # Create a parser instance with the tokens parser = Parser(tokens) # Parse and evaluate the expression result = parser.parse_expression() # Ensure all tokens have been consumed if not parser.is_end(): raise ValueError("Unexpected tokens at the end of the expression") 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 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 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | import math def evaluate(expression): """ Evaluates an arithmetic expression with support for +, -, *, /, parentheses, and prefix operators 'sin' and 'cos'. Assumes that functions take arguments in radians. Example: evaluate("sin(3 + 2 * 4) - cos(15)") # Returns approximately -0.240302 """ def tokenize(expr): """ Converts the input string into a list of tokens. Tokens can be numbers, operators, parentheses, or function names. """ tokens = [] i = 0 while i < len(expr): if expr[i].isspace(): i += 1 continue elif expr[i].isdigit(): num = expr[i] i += 1 while i < len(expr) and expr[i].isdigit(): num += expr[i] i += 1 tokens.append(num) elif expr[i].isalpha(): ident = expr[i] i += 1 while i < len(expr) and expr[i].isalpha(): ident += expr[i] i += 1 if ident in ('sin', 'cos'): tokens.append(ident) else: raise ValueError(f"Unknown identifier: {ident}") elif expr[i] in '+-*/()': tokens.append(expr[i]) i += 1 else: raise ValueError(f"Unknown character: {expr[i]}") return tokens class Parser: """ Implements a recursive descent parser based on the provided BNF grammar. """ def __init__(self, tokens): self.tokens = tokens self.pos = 0 def is_end(self): return self.pos >= len(self.tokens) def current_token(self): if self.is_end(): return None return self.tokens[self.pos] def consume(self, expected=None): tok = self.current_token() if expected and tok != expected: raise ValueError(f"Expected '{expected}', got '{tok}'") self.pos += 1 return tok def parse_expression(self): """ Parses <expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term> """ value = self.parse_term() while not self.is_end() and self.current_token() in ('+', '-'): op = self.consume() term = self.parse_term() if op == '+': value += term else: value -= term return value def parse_term(self): """ Parses <term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor> """ value = self.parse_factor() while not self.is_end() and self.current_token() in ('*', '/'): op = self.consume() factor = self.parse_factor() if op == '*': value *= factor else: if factor == 0: raise ZeroDivisionError("Division by zero") value /= factor return value def parse_factor(self): """ Parses <factor> ::= <number> | '(' <expression> ')' | <prefix-op> <factor> """ tok = self.current_token() if tok in ('sin', 'cos'): op = self.consume() factor = self.parse_factor() if op == 'sin': return math.sin(factor) else: return math.cos(factor) elif tok == '(': self.consume('(') value = self.parse_expression() self.consume(')') return value else: return self.parse_number() def parse_number(self): """ Parses <number> ::= <digit> | <number> <digit> """ tok = self.consume() if not tok.isdigit(): raise ValueError(f"Expected number, got '{tok}'") return float(tok) # Tokenize the input expression tokens = tokenize(expression) # Create a parser instance with the tokens parser = Parser(tokens) # Parse and evaluate the expression result = parser.parse_expression() # Ensure all tokens have been consumed if not parser.is_end(): raise ValueError("Unexpected tokens at the end of the expression") 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