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