caleb531 / expression-validator Goto Github PK

#!/usr/bin/env python3

import unittest


class InvalidExpressionError(Exception):
    pass


# A pushdown automata (PDA) which validates an arithmetic expression
class ExpressionValidator(object):

    identifiers = set('0123456789xyz')
    operators = set('+-*/')

    def __init__(self):
        # State 0: no input read
        # State 1: identifier encountered
        # State 2: operator encountered
        # State 3: all input read (only if in state 1 and Z is atop stack)
        # Parens trigger a stack change, but not a state change
        self.current_state = 0
        self.stack = ['Z']

    def read_symbol(self, symbol):

        if self.current_state != 1 and symbol in self.__class__.identifiers:
            self.current_state = 1
        elif self.current_state != 1 and symbol == '(':
            self.stack.append('(')
        elif self.current_state == 1 and symbol == ')' and self.stack:
            self.stack.pop()
        elif self.current_state == 1 and symbol in self.__class__.operators:
            self.current_state = 2
        elif self.current_state == 2 and symbol in self.__class__.identifiers:
            self.current_state = 1
        elif symbol != ' ':
            raise InvalidExpressionError(
                'Symbol read (\'{}\') produces an invalid expression'.format(
                    symbol))

    def validate(self, expression):

        self.current_state = 0
        self.stack[:] = ['Z']

        for symbol in expression:
            self.read_symbol(symbol)

        if self.current_state == 1 and len(self.stack) == 1:
            self.current_state = 3
            return True
        else:
            raise InvalidExpressionError('PDA never reached final state')


class TestExpressionValidator(unittest.TestCase):

    def setUp(self):
        self.validator = ExpressionValidator()

    def test_valid_expression_1(self):
        self.assertTrue(self.validator.validate('(x * y / (3 + z))'))

    def test_valid_expression_2(self):
        self.assertTrue(self.validator.validate('3 + 4 * 5'))

    def test_valid_expression_3(self):
        self.assertTrue(self.validator.validate('x * x * x'))

    def test_valid_expression_identifier_only(self):
        self.assertTrue(self.validator.validate('x'))

    def test_invalid_expression_1(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('z )(3 ** y')

    def test_invalid_expression_2(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('f * x )')

    def test_invalid_expression_3(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('/ 5 y')

    def test_invalid_expression_3_1(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('3 / 5 y')

    def test_invalid_expression_4(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('((( z + 3 - x)')

    def test_invalid_expression_empty(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('')

    def test_invalid_expression_open_paren(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('3(+2)')

    def test_invalid_expression_close_paren(self):
        with self.assertRaises(InvalidExpressionError):
            self.validator.validate('(3+)2')


if __name__ == '__main__':
    unittest.main()