a recursive descent parser in python


  • 0
    Y
    class EquationInterpreter(object):
        """Equation interpreter:
           Grammar:
                equation := expression '=' expression
                expression := ['-'] term { (+|-) term }
                term := number | variable
                number := digit {digit}
                digit := 0-9
                variable := [number] 'x'
        """
    
        def __init__(self, equation):
            self.next_index = 0
            self.equation = equation
            self.EOF = '\0'
    
        def peek(self):
            if self.next_index < len(self.equation):
                return self.equation[self.next_index]
            else:
                return self.EOF
    
        def consume(self):
            value = self.peek()
            self.next_index = self.next_index + 1
            return self.peek()
    
        def expression(self):
            coefficient, value = self.term()
    
            while True:
                if self.peek() == '+':
                    self.consume()
                    coefficient, value = map(add,
                                             (coefficient, value),
                                             self.term())
                elif self.peek() == '-':
                    self.consume()
                    coefficient, value = map(sub,
                                             (coefficient, value),
                                             self.term())
                else:
                    break
    
            return coefficient, value
    
        def term(self):
            sign = 1
            if self.peek() == '-':
                self.consume()
                sign = -1
    
            number = sign * (self.number() if self.peek().isdigit() else 1)
    
            if self.peek() == 'x':
                self.consume()
                return number, 0
            else:
                return 0, number
    
        def number(self):
            value = 0
            while self.peek().isdigit():
                value = value * 10 + int(self.peek())
                self.consume()
            return value
    
        def interpret(self):
            result_left = self.expression()
            print(result_left)
            self.consume()
            result_right = self.expression()
            print(result_right)
            return map(sub, result_left, result_right)
    
    
    class Solution(object):
        def solveEquation(self, equation):
            """
            :type equation: str
            :rtype: str
            """
    
            interpreter = EquationInterpreter(equation)
    
            coefficient, value = interpreter.interpret()
    
            if coefficient == 0:
                if value != 0:
                    return "No solution"
                else:
                    return "Infinite solutions"
            else:
                return "x={}".format(-value / coefficient)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.