| 1 | 1 | class StackUnderflowError(Exception): |
| 2 | | pass |
| 2 | """Exception raised when Stack is not full. |
| 3 | message: explanation of the error. |
| 4 | """ |
| 5 | def __init__(self, message): |
| 6 | self.message = message |
| 7 | |
| 8 | |
| 9 | def execute_custom_word(word, stack, definitions, definition_history=None, depth=0): |
| 10 | """Execute a custom word with recursion depth protection.""" |
| 11 | if depth > 100: # Prevent infinite recursion |
| 12 | raise ValueError("undefined operation") |
| 13 | |
| 14 | if definition_history is None: |
| 15 | definition_history = {} |
| 16 | |
| 17 | word_lower = word.lower() |
| 18 | if word_lower not in definitions: |
| 19 | return False |
| 20 | |
| 21 | # Get the definition at the time this word was defined |
| 22 | definition = definitions[word_lower] |
| 23 | |
| 24 | # Execute each token in the definition |
| 25 | for token in definition: |
| 26 | token_lower = token.lower() |
| 27 | |
| 28 | # Handle numbers |
| 29 | if token_lower.lstrip('-').isdigit(): |
| 30 | stack.append(int(token_lower)) |
| 31 | # Handle built-in operations |
| 32 | elif token_lower == '+': |
| 33 | if len(stack) < 2: |
| 34 | raise StackUnderflowError("Insufficient number of items in stack") |
| 35 | b = stack.pop() |
| 36 | a = stack.pop() |
| 37 | stack.append(a + b) |
| 38 | elif token_lower == '-': |
| 39 | if len(stack) < 2: |
| 40 | raise StackUnderflowError("Insufficient number of items in stack") |
| 41 | b = stack.pop() |
| 42 | a = stack.pop() |
| 43 | stack.append(a - b) |
| 44 | elif token_lower == '*': |
| 45 | if len(stack) < 2: |
| 46 | raise StackUnderflowError("Insufficient number of items in stack") |
| 47 | b = stack.pop() |
| 48 | a = stack.pop() |
| 49 | stack.append(a * b) |
| 50 | elif token_lower == '/': |
| 51 | if len(stack) < 2: |
| 52 | raise StackUnderflowError("Insufficient number of items in stack") |
| 53 | b = stack.pop() |
| 54 | if b == 0: |
| 55 | raise ZeroDivisionError("divide by zero") |
| 56 | a = stack.pop() |
| 57 | stack.append(int(a / b)) |
| 58 | elif token_lower == 'dup': |
| 59 | if len(stack) < 1: |
| 60 | raise StackUnderflowError("Insufficient number of items in stack") |
| 61 | stack.append(stack[-1]) |
| 62 | elif token_lower == 'drop': |
| 63 | if len(stack) < 1: |
| 64 | raise StackUnderflowError("Insufficient number of items in stack") |
| 65 | stack.pop() |
| 66 | elif token_lower == 'swap': |
| 67 | if len(stack) < 2: |
| 68 | raise StackUnderflowError("Insufficient number of items in stack") |
| 69 | stack[-1], stack[-2] = stack[-2], stack[-1] |
| 70 | elif token_lower == 'over': |
| 71 | if len(stack) < 2: |
| 72 | raise StackUnderflowError("Insufficient number of items in stack") |
| 73 | stack.append(stack[-2]) |
| 74 | # Handle custom words (recursive) |
| 75 | elif token_lower in definitions: |
| 76 | # If this is a recursive call to the same word, use previous definition if available |
| 77 | if token_lower == word and token_lower in definition_history and definition_history[token_lower]: |
| 78 | # Use the previous definition for recursive call |
| 79 | prev_def = definition_history[token_lower][-1] |
| 80 | for prev_token in prev_def: |
| 81 | prev_token_lower = prev_token.lower() |
| 82 | if prev_token_lower.lstrip('-').isdigit(): |
| 83 | stack.append(int(prev_token_lower)) |
| 84 | elif prev_token_lower == '+': |
| 85 | if len(stack) < 2: |
| 86 | raise StackUnderflowError("Insufficient number of items in stack") |
| 87 | b = stack.pop() |
| 88 | a = stack.pop() |
| 89 | stack.append(a + b) |
| 90 | elif prev_token_lower == '-': |
| 91 | if len(stack) < 2: |
| 92 | raise StackUnderflowError("Insufficient number of items in stack") |
| 93 | b = stack.pop() |
| 94 | a = stack.pop() |
| 95 | stack.append(a - b) |
| 96 | elif prev_token_lower == '*': |
| 97 | if len(stack) < 2: |
| 98 | raise StackUnderflowError("Insufficient number of items in stack") |
| 99 | b = stack.pop() |
| 100 | a = stack.pop() |
| 101 | stack.append(a * b) |
| 102 | elif prev_token_lower == '/': |
| 103 | if len(stack) < 2: |
| 104 | raise StackUnderflowError("Insufficient number of items in stack") |
| 105 | b = stack.pop() |
| 106 | if b == 0: |
| 107 | raise ZeroDivisionError("divide by zero") |
| 108 | a = stack.pop() |
| 109 | stack.append(int(a / b)) |
| 110 | elif prev_token_lower == 'dup': |
| 111 | if len(stack) < 1: |
| 112 | raise StackUnderflowError("Insufficient number of items in stack") |
| 113 | stack.append(stack[-1]) |
| 114 | elif prev_token_lower == 'drop': |
| 115 | if len(stack) < 1: |
| 116 | raise StackUnderflowError("Insufficient number of items in stack") |
| 117 | stack.pop() |
| 118 | elif prev_token_lower == 'swap': |
| 119 | if len(stack) < 2: |
| 120 | raise StackUnderflowError("Insufficient number of items in stack") |
| 121 | stack[-1], stack[-2] = stack[-2], stack[-1] |
| 122 | elif prev_token_lower == 'over': |
| 123 | if len(stack) < 2: |
| 124 | raise StackUnderflowError("Insufficient number of items in stack") |
| 125 | stack.append(stack[-2]) |
| 126 | elif prev_token_lower in definitions: |
| 127 | execute_custom_word(prev_token_lower, stack, definitions, definition_history, depth + 1) |
| 128 | else: |
| 129 | raise ValueError("undefined operation") |
| 130 | else: |
| 131 | execute_custom_word(token_lower, stack, definitions, definition_history, depth + 1) |
| 132 | else: |
| 133 | raise ValueError("undefined operation") |
| 134 | |
| 135 | return True |
| 3 | 136 | |
| 4 | 137 | |
| 5 | 138 | def evaluate(input_data): |
| 6 | | pass |
| 139 | stack = [] |
| 140 | definitions = {} |
| 141 | definition_history = {} |
| 142 | |
| 143 | # Edge Case: Empty input data |
| 144 | if not input_data: |
| 145 | return [] |
| 146 | |
| 147 | for line in input_data: |
| 148 | tokens = line.split() |
| 149 | i = 0 |
| 150 | while i < len(tokens): |
| 151 | token = tokens[i].lower() |
| 152 | |
| 153 | # Handle number |
| 154 | if token.lstrip('-').isdigit(): |
| 155 | stack.append(int(token)) |
| 156 | i += 1 |
| 157 | continue |
| 158 | |
| 159 | # Handle custom word definition |
| 160 | if token == ':': |
| 161 | # Edge Case: Malformed definition - missing word name |
| 162 | if i + 1 >= len(tokens): |
| 163 | raise ValueError("undefined operation") |
| 164 | |
| 165 | word_name = tokens[i+1].lower() |
| 166 | |
| 167 | # Edge Case: Redefining a number |
| 168 | if word_name.lstrip('-').isdigit(): |
| 169 | raise ValueError("illegal operation") |
| 170 | |
| 171 | # Edge Case: Malformed definition - missing semicolon |
| 172 | if ';' not in tokens[i+2:]: |
| 173 | raise ValueError("undefined operation") |
| 174 | |
| 175 | semicolon_index = tokens.index(';', i+2) |
| 176 | definition = tokens[i+2:semicolon_index] |
| 177 | |
| 178 | # Expand any custom words in the definition to their current definitions |
| 179 | expanded_definition = [] |
| 180 | for token in definition: |
| 181 | token_lower = token.lower() |
| 182 | if token_lower in definitions: |
| 183 | # Expand to the current definition of this word |
| 184 | expanded_definition.extend(definitions[token_lower]) |
| 185 | else: |
| 186 | expanded_definition.append(token) |
| 187 | |
| 188 | # Store previous definition in history if it exists |
| 189 | if word_name in definitions: |
| 190 | if word_name not in definition_history: |
| 191 | definition_history[word_name] = [] |
| 192 | definition_history[word_name].append(definitions[word_name]) |
| 193 | definitions[word_name] = expanded_definition |
| 194 | i = semicolon_index + 1 |
| 195 | continue |
| 196 | |
| 197 | # Handle custom words |
| 198 | if token in definitions: |
| 199 | # Execute the custom word directly |
| 200 | if not execute_custom_word(token, stack, definitions, definition_history): |
| 201 | raise ValueError("undefined operation") |
| 202 | i += 1 |
| 203 | continue |
| 204 | |
| 205 | # Handle stack operations |
| 206 | if token == '+': |
| 207 | # Edge Case: Insufficient stack items for addition |
| 208 | if len(stack) < 2: |
| 209 | raise StackUnderflowError("Insufficient number of items in stack") |
| 210 | b = stack.pop() |
| 211 | a = stack.pop() |
| 212 | stack.append(a + b) |
| 213 | elif token == '-': |
| 214 | # Edge Case: Insufficient stack items for subtraction |
| 215 | if len(stack) < 2: |
| 216 | raise StackUnderflowError("Insufficient number of items in stack") |
| 217 | b = stack.pop() |
| 218 | a = stack.pop() |
| 219 | stack.append(a - b) |
| 220 | elif token == '*': |
| 221 | # Edge Case: Insufficient stack items for multiplication |
| 222 | if len(stack) < 2: |
| 223 | raise StackUnderflowError("Insufficient number of items in stack") |
| 224 | b = stack.pop() |
| 225 | a = stack.pop() |
| 226 | stack.append(a * b) |
| 227 | elif token == '/': |
| 228 | # Edge Case: Insufficient stack items for division |
| 229 | if len(stack) < 2: |
| 230 | raise StackUnderflowError("Insufficient number of items in stack") |
| 231 | # Edge Case: Division by zero |
| 232 | b = stack.pop() |
| 233 | if b == 0: |
| 234 | raise ZeroDivisionError("divide by zero") |
| 235 | a = stack.pop() |
| 236 | stack.append(int(a / b)) |
| 237 | elif token == 'dup': |
| 238 | # Edge Case: Insufficient stack items for DUP |
| 239 | if len(stack) < 1: |
| 240 | raise StackUnderflowError("Insufficient number of items in stack") |
| 241 | stack.append(stack[-1]) |
| 242 | elif token == 'drop': |
| 243 | # Edge Case: Insufficient stack items for DROP |
| 244 | if len(stack) < 1: |
| 245 | raise StackUnderflowError("Insufficient number of items in stack") |
| 246 | stack.pop() |
| 247 | elif token == 'swap': |
| 248 | # Edge Case: Insufficient stack items for SWAP |
| 249 | if len(stack) < 2: |
| 250 | raise StackUnderflowError("Insufficient number of items in stack") |
| 251 | stack[-1], stack[-2] = stack[-2], stack[-1] |
| 252 | elif token == 'over': |
| 253 | # Edge Case: Insufficient stack items for OVER |
| 254 | if len(stack) < 2: |
| 255 | raise StackUnderflowError("Insufficient number of items in stack") |
| 256 | stack.append(stack[-2]) |
| 257 | else: |
| 258 | # Edge Case: Undefined operation |
| 259 | raise ValueError("undefined operation") |
| 260 | |
| 261 | i += 1 |
| 262 | |
| 263 | return stack |
| 264 | # Handled Edge Cases: Empty input data, Malformed definition - missing word name, Redefining a number, Malformed definition - missing semicolon, Insufficient stack items for addition, Insufficient stack items for subtraction, Insufficient stack items for multiplication, Insufficient stack items for division, Division by zero, Insufficient stack items for DUP, Insufficient stack items for DROP, Insufficient stack items for SWAP, Insufficient stack items for OVER, Undefined operation |