Implemented as a demonstration for a CodeReview.SE question.
See my answer for more details.
Also don't do modules like I have in this gist! They should all be contained in a module like calculator, but that doesn't fit well
with the gist format.
calculate('3 * (1 + 6 / 3)')
| from peekable_iterator import PeekableIterator | |
| class BaseParser: | |
| """A base class containing utilities useful for a Parser.""" | |
| def __init__(self, items): | |
| self._items = PeekableIterator(items) | |
| def _take(self, predicate): | |
| """ | |
| Yields a contiguous group of items from the items being parsed for | |
| which the predicate returns True. | |
| >>> p = BaseParser([2, 4, 3]) | |
| >>> list(p._take(lambda x: x % 2 == 0)) | |
| [2, 4] | |
| """ | |
| while predicate(self._items.peek()): | |
| yield next(self._items) | |
| def _done(self): | |
| """Returns True if the underlying items have been fully consumed.""" | |
| try: | |
| self._items.peek() | |
| return False | |
| except StopIteration: | |
| return True |
| from parser import Parser | |
| from scanner import Scanner | |
| from calculator_exceptions import CalculatorException | |
| def calculate(expression): | |
| """Evaluates a mathematical expression and returns the result. | |
| >>> calculate('3 * (1 + 6 / 3)') | |
| 9 | |
| """ | |
| return Parser(Scanner(expression).scan()).parse() | |
| if __name__ == '__main__': | |
| # For demo purposes... | |
| while True: | |
| try: | |
| print(calculate(input())) | |
| except CalculatorException as e: | |
| print(e) | |
| except KeyboardInterrupt: | |
| break |
| class CalculatorException(Exception): | |
| pass | |
| class BadNumberError(CalculatorException): | |
| def __init__(self, number): | |
| super().__init__("unable to scan number: {}".format(number)) | |
| class UnexpectedCharacterError(CalculatorException): | |
| def __init__(self, char, expected=[]): | |
| if expected: | |
| super().__init__("unexpected character {}, expected: {}" | |
| .format(repr(char), repr(expected))) | |
| else: | |
| super().__init__("unexpected character: {}".format(char)) | |
| class UnexpectedEndError(CalculatorException): | |
| def __init__(self, expected): | |
| super().__init__("found end, but expected: {}".format(repr(expected))) |
MIT License
Copyright (c) 2018 Bailey Parker
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
| import operator | |
| from base_parser import BaseParser | |
| from calculator_exceptions import UnexpectedCharacterError, UnexpectedEndError | |
| class Parser(BaseParser): | |
| """Parser for tokenized calculator inputs.""" | |
| def parse(self): | |
| """Parse calculator input and return the result of evaluating it. | |
| >>> Parser([1, '*', '(', 2, '+', 3, ')']).parse() | |
| 5 | |
| """ | |
| return self._parse_expression() | |
| def _parse_expression(self): | |
| """Parse an Expression and return the result of evaluating it. | |
| >>> Parser([1, '+', 2])._parse_expression() | |
| 3 | |
| """ | |
| # Parse the first (required) Term | |
| terms = [self._parse_term()] | |
| # Parse any following: ("*"|"/") Factor | |
| op = lambda t: t in '+-' | |
| terms += flatten((op, self._parse_term()) for op in self._take(op)) | |
| return evaluate(terms) | |
| def _parse_term(self): | |
| """Parse a Term and return the result of evaluating it. | |
| >>> Parser([1, '*', 2])._parse_term() | |
| 2 | |
| """ | |
| # Parse the first (required) Factor | |
| factors = [self._parse_factor()] | |
| # Parse any following: ("*"|"/") Factor | |
| op = lambda t: t in '*/' | |
| factors += flatten((op, self._parse_factor()) for op in self._take(op)) | |
| return evaluate(factors) | |
| def _parse_factor(self): | |
| """Parse a Factor and return the result of evaluating it. | |
| >>> Parser([1])._parse_factor() | |
| 1 | |
| >>> Parser(['(', 1, '+', 2, '*', 3, ')'])._parse_factor() | |
| 7 | |
| """ | |
| # NOTE: Here's where Python gets a little cumbersome. This isn't really | |
| # a for, we're just using it to handle the case where it doesn't | |
| # find a number (gracefully skip). If it finds one, we return the | |
| # number. | |
| for n in self._take(lambda t: isinstance(t, float)): | |
| return n | |
| # If we failed to parse a number, then try to find a '(' | |
| for _ in self._take(lambda t: t == '('): | |
| # If we found a '(', parse the subexpression | |
| value = self._parse_expression() | |
| # Make sure the subexpression is followed by a ')' | |
| self._expect(')') | |
| # Both parsing the number and subexpresion failed | |
| raise self._unexpected('number', '(') | |
| def _expect(self, char): | |
| """Expect a certain character, or raise if it is not next.""" | |
| for _ in self._take(lambda t: t == char): | |
| return | |
| raise self._unexpected(char) | |
| def _unexpected(self, *expected): | |
| """Create an exception for an unexpected character.""" | |
| try: | |
| return UnexpectedCharacterError(self._items.peek(), expected) | |
| except StopIteration: | |
| return UnexpectedEndError(expected) | |
| def evaluate(items): | |
| """ | |
| Evaluate a list of floats separated by operators (at the same level of | |
| precedence). Returns the result. | |
| >>> evaluate([3, '*', 4, '/', 2]) | |
| 6 | |
| """ | |
| assert items, 'cannot evaluate empty list' | |
| # x, x + x, x + x + x, etc. all have an odd number of tokens | |
| assert len(items) % 2 == 1, 'list must be of odd length' | |
| while len(items) > 1: | |
| items[-3:] = [_evaluate_binary(*items[-3:])] | |
| return items[0] | |
| def _evaluate_binary(lhs, op, rhs): | |
| """Evalutates a single binary operation op where lhs and rhs are floats.""" | |
| ops = {'+': operator.add, | |
| '-': operator.sub, | |
| '*': operator.mul, | |
| '/': operator.truediv} | |
| return ops[op](lhs, rhs) | |
| def flatten(iterable): | |
| """Flattens a nested iterable by one nesting layer. | |
| >>> flatten([[1,2], [3]]) | |
| [1, 2, 3] | |
| """ | |
| return [x for l in iterable for x in l] |
| class PeekableIterator: | |
| """An iterator that supports 1-lookahead (peek).""" | |
| def __init__(self, iterable): | |
| self._iterator = iter(iterable) | |
| # NOTE: We use None here to denote that we haven't peeked yet. This | |
| # doesn't work if None can occur in the iterable (so this | |
| # doesn't generalize!), but for our purposes here it's fine! | |
| self._next_item = None | |
| def peek(self): | |
| """ | |
| Return the next item that will be returned by the iterator without | |
| advancing the iterator. Raises StopIteration if the iterator is done. | |
| >>> i = PeekableIterator([1, 2, 3]) | |
| >>> i.peek() | |
| 1 | |
| >>> i.peek() | |
| 1 | |
| >>> next(i) | |
| 1 | |
| >>> next(i) | |
| 2 | |
| >>> i.peek() | |
| 3 | |
| """ | |
| if self._next_item is None: | |
| self._next_item = next(self._iterator) | |
| return self._next_item | |
| def __next__(self): | |
| if self._next_item is not None: | |
| next_item = self._next_item | |
| self._next_item = None | |
| return next_item | |
| return next(self._iterator) | |
| def __iter__(self): | |
| return self |
| from base_parser import BaseParser | |
| from calculator_exceptions import BadNumberError, UnexpectedCharacterError | |
| class Scanner(BaseParser): | |
| """Scanner scans an input string for calculator tokens and yields them. | |
| >>> list(Scanner('11 * (2 + 3)').scan()) | |
| [11, '(', 2, '+', 3, ')'] | |
| """ | |
| def scan(self): | |
| """Yields all tokens in the input.""" | |
| while not self._done(): | |
| # Parser combinators, you don't need this explicit check, but alas | |
| self._check_for_unexpected_char() | |
| # Ignore any whitespace that may be next | |
| self._consume_whitespace() | |
| # Emit any symbol tokens that may be next | |
| yield from self._take(lambda char: char in '+-*/()') | |
| # Emit any number token that may be next | |
| yield from self._take_number() | |
| def _check_for_unexpected_char(self): | |
| ops = '.+-*/()' | |
| unexpected = lambda c: not (c.isdigit() or c.isspace() or c in ops) | |
| unexpected_chars = list(self._take(unexpected)) | |
| if unexpected_chars: | |
| raise UnexpectedCharacterError(''.join(unexpected_chars[:1])) | |
| def _consume_whitespace(self): | |
| """_take()s whitespace characters, but does not yield them.""" | |
| # Note we need the list here to force evaluation of the generator | |
| list(self._take(lambda char: char.isspace())) | |
| def _take_number(self): | |
| """Yields a single number if there is one next in the input.""" | |
| # Gather up the digits/. forming the next number in the input | |
| number = ''.join(self._take(lambda c: c.isdigit() or c == '.')) | |
| # If number is empty, we didn't scan digits, so don't try to float it | |
| if number: | |
| try: | |
| yield float(number) | |
| except ValueError: | |
| raise BadNumberError(number) | |
| if __name__ == '__main__': | |
| # For demo purposes... | |
| while True: | |
| print(list(Scanner(input()).scan())) |