Coverage for blog/dsa/leetcode/parentheses/__init__.py: 62%

1from typing import Iterator 

2 

3import pytest 

4 

5 

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 

18 

19 for k in range(n - 1): 

20 

21 head = pieces[k] 

22 next = pieces[k + 1] 

23 new = ("(" + head[0] + head[1] + next[0] + ")", next[1]) 

24 

25 self.conquer([*pieces[0:k], new, *pieces[k + 2 :]], answers) 

26 

27 def parse(self, expression: str) -> list[tuple[str, str]]: 

28 pieces = [] 

29 

30 current = "" 

31 for char in expression: 

32 

33 if char.isnumeric(): 

34 current += char 

35 else: 

36 pieces.append((current, char)) 

37 current = "" 

38 

39 pieces.append((current, "")) 

40 return pieces 

41 

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 

47 

48 

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 

62 

63 answers.add(exp) 

64 yield eval(exp) 

65 return 

66 

67 for k in range(n - 1): 

68 

69 new = ( 

70 "(" + pieces[k][0] + pieces[k][1] + pieces[k + 1][0] + ")", 

71 pieces[k + 1][1], 

72 ) 

73 

74 yield from self.conquer( 

75 *pieces[0:k], new, *pieces[k + 2 :], answers=answers 

76 ) 

77 

78 def parse(self, expression: str) -> Iterator[tuple[str, str]]: 

79 

80 current = "" 

81 for char in expression: 

82 if char.isnumeric(): 

83 current += char 

84 else: 

85 yield (current, char) 

86 current = "" 

87 

88 yield (current, "") 

89 

90 def diffWaysToCompute(self, expression: str) -> list[int]: 

91 

92 answers: set[str] = set() 

93 return list(self.conquer(*self.parse(expression), answers=answers)) 

94 # end snippet solution_initial 

95 

96 

97@pytest.fixture 

98def solution(): 

99 return Solution() 

100 

101 

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]): 

113 

114 answer = sorted(answer) 

115 answer_computed = sorted(solution.diffWaysToCompute(expression)) 

116 print(answer, answer_computed) 

117 assert answer == answer_computed