Coverage for blog/dsa/leetcode/parentheses/__init__.py: 62%
69 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1from typing import Iterator
3import pytest
6# start snippet solution_initial
7class SolutionInitial:
8 def conquer(self, pieces: list[tuple[str, str]], answers: set[str]):
9 n = len(pieces)
10 if n == 1:
11 answers.add(pieces[0][0])
12 return
13 if n == 2:
14 head, next = pieces[0], pieces[1]
15 exp = head[0] + head[1] + next[0]
16 answers.add(exp)
17 return
19 for k in range(n - 1):
21 head = pieces[k]
22 next = pieces[k + 1]
23 new = ("(" + head[0] + head[1] + next[0] + ")", next[1])
25 self.conquer([*pieces[0:k], new, *pieces[k + 2 :]], answers)
27 def parse(self, expression: str) -> list[tuple[str, str]]:
28 pieces = []
30 current = ""
31 for char in expression:
33 if char.isnumeric():
34 current += char
35 else:
36 pieces.append((current, char))
37 current = ""
39 pieces.append((current, ""))
40 return pieces
42 def diffWaysToCompute(self, expression: str) -> list[int]:
43 pieces = self.parse(expression)
44 self.conquer(pieces, answers := set()) # type: ignore[var-annotated]
45 return list(eval(thing) for thing in answers)
46 # end snippet solution_initial
49# start snippet solution_initial
50# NOTE: Eval and callstack are problems.
51class Solution:
52 def conquer(self, *pieces: tuple[str, str], answers: set[str]):
53 n = len(pieces)
54 if n == 1:
55 yield eval(pieces[0][0])
56 return
57 if n == 2:
58 head, next = pieces[0], pieces[1]
59 exp = head[0] + head[1] + next[0]
60 if exp in answers:
61 return
63 answers.add(exp)
64 yield eval(exp)
65 return
67 for k in range(n - 1):
69 new = (
70 "(" + pieces[k][0] + pieces[k][1] + pieces[k + 1][0] + ")",
71 pieces[k + 1][1],
72 )
74 yield from self.conquer(
75 *pieces[0:k], new, *pieces[k + 2 :], answers=answers
76 )
78 def parse(self, expression: str) -> Iterator[tuple[str, str]]:
80 current = ""
81 for char in expression:
82 if char.isnumeric():
83 current += char
84 else:
85 yield (current, char)
86 current = ""
88 yield (current, "")
90 def diffWaysToCompute(self, expression: str) -> list[int]:
92 answers: set[str] = set()
93 return list(self.conquer(*self.parse(expression), answers=answers))
94 # end snippet solution_initial
97@pytest.fixture
98def solution():
99 return Solution()
102@pytest.mark.parametrize(
103 "expression, answer",
104 (
105 (("2+5"), [7]),
106 ("2-1-1", [0, 2]),
107 ("2+3*5-4", [5, 5, 13, 13, 21]),
108 ("2*3-4*5", [-34, -14, -10, -10, 10]),
109 ("0", [0]),
110 ),
111)
112def test_solution(solution: Solution, expression: str, answer: list[int]):
114 answer = sorted(answer)
115 answer_computed = sorted(solution.diffWaysToCompute(expression))
116 print(answer, answer_computed)
117 assert answer == answer_computed