caleb531 / expression-validator Goto Github PK
View Code? Open in Web Editor NEWValidates the syntax of arithmetic expressions
Validates the syntax of arithmetic expressions
Hi, @BrittDibble. I recently got a few ideas for how to write the PDA for this assignment, and I decided to write up an implementation of my approach in Python:
I've also written some tests using the same examples from the assignment prompt (plus a few of my own) to ensure that the PDA works correctly. Currently, all 12 tests are passing, so I think this algorithm will totally work for the assignment. Of course, we still need to write the logic for reading input from the user or from a file. I'll also welcome and suggestions you have. :)
Thoughts?
#!/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()
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.