Simple Arithmetic Expression Parser using PEG in Python

This challenge asks you to implement a basic parser for arithmetic expressions using the PEG (Parsing Expression Grammar) formalism in Python. PEG parsers offer a clear and declarative way to define grammars, and this exercise will help you understand their principles and implementation. The parser should handle addition, subtraction, multiplication, and division with integer operands.

Problem Description

You are to create a Python class PEGParser that can parse arithmetic expressions defined by the following grammar:

expression = term , { ("+" | "-") , term } ;
term       = factor, { ("*" | "/") , factor } ;
factor     = integer | "(" , expression , ")" ;
integer    = [0-9]+ ;

The parser should take a string representing the arithmetic expression as input and return the result of evaluating the expression. The parser must handle operator precedence correctly (multiplication and division before addition and subtraction) and parentheses for grouping. Error handling is required; the parser should raise a ValueError if the input string is not a valid expression according to the grammar.

Key Requirements:

• PEG Implementation: The core of the solution must be a PEG-based parser. You can use a library like parsimonious or implement the PEG parsing logic yourself (though using parsimonious is highly recommended for efficiency and clarity).
• Operator Precedence: Multiplication and division should be evaluated before addition and subtraction.
• Parentheses: Parentheses should be correctly handled to override the default operator precedence.
• Integer Operands: The parser should only support integer operands.
• Error Handling: The parser should raise a ValueError for invalid input expressions.
• Evaluation: The parser should evaluate the parsed expression and return the integer result.

Expected Behavior:

The PEGParser class should have a method parse(expression_string) that takes a string as input and returns an integer. If the input is a valid expression, the method should return the result of evaluating the expression. If the input is invalid, the method should raise a ValueError with a descriptive message.

Edge Cases to Consider:

• Empty input string.
• Invalid characters in the input string (e.g., letters, floating-point numbers).
• Division by zero.
• Unmatched parentheses.
• Expressions with only one operand.
• Multiple consecutive operators (e.g., "2++3").

Examples

Example 1:

Input: "2 + 3 * 4"
Output: 14
Explanation: Multiplication is performed before addition: (2 + (3 * 4)) = (2 + 12) = 14

Example 2:

Input: "(2 + 3) * 4"
Output: 20
Explanation: Parentheses override operator precedence: ((2 + 3) * 4) = (5 * 4) = 20

Example 3:

Input: "10 / 2 - 1"
Output: 4
Explanation: Division is performed before subtraction: (10 / 2 - 1) = (5 - 1) = 4

Example 4:

Input: "5"
Output: 5
Explanation: A single integer is a valid expression.

Example 5:

Input: "2 + (3 * (4 - 1))"
Output: 11
Explanation: Nested parentheses and operator precedence are correctly handled.

Example 6:

Input: "2 + a"
Output:
ValueError: Invalid character 'a' in expression.

Example 7:

Input: "10 / 0"
Output:
ValueError: Division by zero.

Constraints

• Input String Length: The input expression string will be no longer than 256 characters.
• Integer Range: Integer operands will be within the range of -1000 to 1000.
• Performance: The parsing process should complete within 0.1 seconds for valid expressions.
• Input Format: The input string will consist of integers, operators (+, -, *, /), parentheses, and whitespace. Whitespace should be ignored.

Notes

• Consider using a recursive descent parsing approach, which is a common technique for implementing PEG parsers.
• The parsimonious library provides a convenient way to define and parse PEGs in Python. If you choose to implement the parsing logic yourself, be mindful of potential backtracking issues that can arise with ambiguous grammars.
• Think about how to represent the parsed expression internally (e.g., as an abstract syntax tree) to facilitate evaluation.
• Focus on clear and well-documented code. Error messages should be informative and helpful for debugging.
• Remember to handle division by zero gracefully.
• Whitespace should be ignored during parsing.
• The grammar is left-recursive. If implementing manually, you'll need to transform it to be right-recursive. parsimonious handles this automatically.