1"""Evaluate simplification expressions."""
2import collections.abc
3import enum
4import re
5import string
6import typing
7
8import pydantic
9
10from .calculator_sub_package import BinaryArithmeticOperator, calculate_results
11
12
[docs]
13@enum.unique
14class Parentheses(str, enum.Enum):
15 """Define supported brackets."""
16
17 LEFT = "("
18 RIGHT = ")"
19
20
21@enum.unique
22class TokenType(str, enum.Enum):
23 """Define supported token types."""
24
25 POSITIVE_NUMBER = "positive_number"
26 NEGATIVE_NUMBER = "negative_number"
27 OPERATOR = "operator"
28 LEFT_PARENTHESIS = "left_parenthesis"
29 RIGHT_PARENTHESIS = "right_parenthesis"
30
31
32SUPPORTED_CHARACTERS = set.union(
33 set(string.digits + "."), set(BinaryArithmeticOperator), set(Parentheses)
34)
35ACCEPTABLE_CHARACTERS = set(" ")
36
37REGULAR_EXPRESSION_PATTERNS = {
38 TokenType.POSITIVE_NUMBER: r"\d+(?:\.\d+)?",
39 TokenType.NEGATIVE_NUMBER: rf"(?<![\d|{Parentheses.RIGHT.value}])-\d+(?:\.\d+)?",
40 TokenType.OPERATOR: (
41 "[" + "".join(rf"\{operator.value}" for operator in BinaryArithmeticOperator) + "]"
42 ),
43 TokenType.LEFT_PARENTHESIS: rf"\{Parentheses.LEFT.value}",
44 TokenType.RIGHT_PARENTHESIS: rf"\{Parentheses.RIGHT.value}",
45}
46SUPPORTED_TOKEN_PATTERN = "|".join(
47 f"(?P<{token_type.value}>{token_pattern})"
48 for token_type, token_pattern in REGULAR_EXPRESSION_PATTERNS.items()
49)
50
51OPERATION_PRECEDENCES: dict[BinaryArithmeticOperator | Parentheses, int] = {
52 Parentheses.LEFT: 0,
53 Parentheses.RIGHT: 0,
54 BinaryArithmeticOperator.ADDITION: 1,
55 BinaryArithmeticOperator.SUBTRACTION: 1,
56 BinaryArithmeticOperator.MULTIPLICATION: 2,
57 BinaryArithmeticOperator.DIVISION: 2,
58}
59
60
[docs]
61@pydantic.validate_call(validate_return=True)
62def clean_and_tokenise_expression(
63 raw_expression: str,
64) -> pydantic.InstanceOf[collections.abc.Iterator[re.Match[str]]]:
65 """Extract tokens from arithmetic expression after pre-processing.
66
67 Parameters
68 ----------
69 raw_expression : str
70 infix expression
71
72 Returns
73 -------
74 collections.abc.Iterator[re.Match[str]]
75 tokens in standard arithmetic expression
76
77 Raises
78 ------
79 ValueError
80 if unsupported characters are passed
81 """
82 clean_expression = raw_expression.translate(
83 str.maketrans(dict.fromkeys(ACCEPTABLE_CHARACTERS, None))
84 )
85
86 if unsupported_characters := set(clean_expression).difference(SUPPORTED_CHARACTERS):
87 raise ValueError(f"Unexpected characters: {unsupported_characters}")
88
89 tokens = re.finditer(SUPPORTED_TOKEN_PATTERN, clean_expression)
90
91 return tokens
92
93
[docs]
94@pydantic.validate_call(validate_return=True)
95def convert_infix_expression( # noqa: C901 # skipcq: PY-R1000
96 infix_expression_tokens: pydantic.InstanceOf[collections.abc.Iterator[re.Match[str]]],
97) -> list[BinaryArithmeticOperator | float]:
98 """Convert standard arithmetic expression into reverse Polish notation.
99
100 This implements shunting yard algorithm following pseudocode section in Wikipedia.
101
102 Parameters
103 ----------
104 infix_expression_tokens : collections.abc.Iterator[re.Match[str]]
105 tokens in standard arithmetic expression
106
107 Returns
108 -------
109 list[BinaryArithmeticOperator | float]
110 postfix arithmetic expression
111
112 Raises
113 ------
114 ValueError
115 if brackets are not matching
116
117 Notes
118 -----
119 #. Initiate operator stack and output queue.
120 #. Modify based on token type.
121
122 * Number
123
124 #. Convert to number (using ``float``).
125 #. Add to ``output_queue``.
126
127 * Operator
128
129 #. Convert to operator (using ``BinaryArithmeticOperator``).
130 #. Move top lower precedence operators from ``operator_stack`` into ``output_queue``.
131 #. Add to ``operator_stack``.
132
133 * Left Parenthesis
134
135 #. Convert to bracket (using ``Parentheses``).
136
137 * Right Parenthesis
138
139 #. Convert to bracket (using ``Parentheses``).
140 #. Move operators from ``operator_stack`` into ``output_queue`` till left bracket.
141 #. Discard left bracket from top of ``operator_stack``.
142
143 References
144 ----------
145 `Wikipedia <https://en.wikipedia.org/wiki/Shunting_yard_algorithm#The_algorithm_in_detail>`_.
146 """
147 operator_stack: list[BinaryArithmeticOperator | typing.Literal[Parentheses.LEFT]] = []
148 output_queue: list[BinaryArithmeticOperator | float] = []
149
150 @pydantic.validate_call
151 def __process_number_token(number_token: str) -> None:
152 """Modify ``output_queue``.
153
154 Parameters
155 ----------
156 number_token : str
157 a real number as a string
158
159 Notes
160 -----
161 #. Convert to number.
162 #. Add to ``output_queue``.
163 """
164 valid_number = float(number_token)
165
166 output_queue.append(valid_number)
167
168 @pydantic.validate_call
169 def __process_operator_token(operator_token: str) -> None:
170 """Modify ``operator_stack`` and ``output_queue``.
171
172 Parameters
173 ----------
174 operator_token : str
175 a binary operator as a string
176
177 Notes
178 -----
179 #. Convert to operator.
180 #. Move previous lower precedence operators from ``operator_stack`` into ``output_queue``.
181 #. Add to ``operator_stack``.
182 """
183 valid_operator = BinaryArithmeticOperator(operator_token)
184
185 while (
186 operator_stack
187 and (last_operator := operator_stack[-1]) != Parentheses.LEFT
188 and OPERATION_PRECEDENCES[last_operator] >= OPERATION_PRECEDENCES[valid_operator]
189 ):
190 _ = operator_stack.pop()
191 output_queue.append(last_operator)
192
193 operator_stack.append(valid_operator)
194
195 @pydantic.validate_call
196 def __process_left_parenthesis_token(parenthesis_token: str) -> None:
197 """Modify ``operator_stack``.
198
199 Parameters
200 ----------
201 parenthesis_token : str
202 left bracket as a string
203
204 Raises
205 ------
206 ValueError
207 if token is not left bracket
208
209 Notes
210 -----
211 #. Convert to bracket.
212 #. Add to ``operator_stack``.
213 """
214 valid_parenthesis = Parentheses(parenthesis_token)
215
216 if valid_parenthesis != Parentheses.LEFT:
217 raise ValueError(f"Unexpected token: {parenthesis_token}") # pragma: no cover
218
219 operator_stack.append(valid_parenthesis)
220
221 @pydantic.validate_call
222 def __process_right_parenthesis_token(parenthesis_token: str) -> None:
223 """Modify ``operator_stack`` and ``output_queue``.
224
225 Parameters
226 ----------
227 parenthesis_token : str
228 right bracket as a string
229
230 Raises
231 ------
232 ValueError
233 if token is not right bracket
234 ValueError
235 if brackets are not matching
236
237 Notes
238 -----
239 #. Convert to bracket.
240 #. Move operators from ``operator_stack`` into ``output_queue`` till left bracket.
241 #. Discard left bracket from top of ``operator_stack``.
242 """
243 valid_parenthesis = Parentheses(parenthesis_token)
244
245 if valid_parenthesis != Parentheses.RIGHT:
246 raise ValueError(f"Unexpected token: {parenthesis_token}") # pragma: no cover
247
248 while operator_stack and (last_operator := operator_stack[-1]) != Parentheses.LEFT:
249 _ = operator_stack.pop()
250 output_queue.append(last_operator)
251
252 if not operator_stack or (last_operator := operator_stack[-1]) != Parentheses.LEFT:
253 raise ValueError("Mismatched right parenthesis")
254
255 _ = operator_stack.pop()
256
257 for token in infix_expression_tokens:
258 try:
259 token_type, token_value = next(
260 (element_type, element_value)
261 for element_type, element_value in token.groupdict().items()
262 if element_value is not None
263 )
264 except StopIteration: # pragma: no cover
265 continue
266
267 match token_type:
268 case TokenType.POSITIVE_NUMBER | TokenType.NEGATIVE_NUMBER:
269 __process_number_token(token_value)
270 case TokenType.OPERATOR:
271 __process_operator_token(token_value)
272 case TokenType.LEFT_PARENTHESIS:
273 __process_left_parenthesis_token(token_value)
274 case TokenType.RIGHT_PARENTHESIS:
275 __process_right_parenthesis_token(token_value)
276
277 while operator_stack:
278 if (last_operator := operator_stack[-1]) is Parentheses.LEFT:
279 raise ValueError("Mismatched left parenthesis")
280
281 _ = operator_stack.pop()
282 output_queue.append(last_operator)
283
284 return output_queue
285
286
[docs]
287@pydantic.validate_call(validate_return=True)
288def evaluate_postfix_expression(
289 postfix_expression: list[BinaryArithmeticOperator | float],
290) -> float:
291 """Evaluate postfix arithmetic expression in reverse Polish notation.
292
293 Parameters
294 ----------
295 postfix_expression : list[BinaryArithmeticOperator | float]
296 elements of arithmetic expression in postfix format
297
298 Returns
299 -------
300 float
301 result of arithmetic expression
302 """
303 stack: list[float] = []
304 for element in postfix_expression:
305 if isinstance(element, float | int):
306 stack.append(element)
307 else:
308 operator = BinaryArithmeticOperator(element)
309
310 second_input = stack.pop()
311 first_input = stack.pop()
312
313 result = calculate_results(first_input, operator, second_input)
314 stack.append(result)
315
316 return stack.pop()
317
318
[docs]
319@pydantic.validate_call(validate_return=True)
320def solve_simplification(expression: str) -> float:
321 """Evaluate arithmetic expression.
322
323 Parameters
324 ----------
325 expression : str
326 standard arithmetic expression
327
328 Returns
329 -------
330 float
331 result of arithmetic expression
332
333 Examples
334 --------
335 .. code-block:: pycon
336
337 >>> from package_name_to_import_with import solve_simplification
338 >>> solve_simplification("0 + 1 - 2 * 3 / 4")
339 -0.5
340 >>> solve_simplification("5 * 6 / (7 + 8) - 9")
341 -7.0
342 """
343 raw_infix_tokens = clean_and_tokenise_expression(expression)
344 ordered_postfix_tokens = convert_infix_expression(raw_infix_tokens)
345 expression_value = evaluate_postfix_expression(ordered_postfix_tokens)
346
347 return expression_value
348
349
350__all__ = [
351 "OPERATION_PRECEDENCES",
352 "Parentheses",
353 "clean_and_tokenise_expression",
354 "convert_infix_expression",
355 "evaluate_postfix_expression",
356 "solve_simplification",
357]