Evaluate a Small Stack-Based Integer Language

Question

The candidate is asked to evaluate a small stack-based integer language by implementing operations such as addition, subtraction, multiplication, division, as well as stack manipulations like swap, duplicate, pop, and drop.

Codemia · Accepted Answer

The task requires implementing a small stack-based language that can process a string of integers and operations. The operations include basic arithmetic and stack manipulation commands. The implementation must handle edge cases like underflow when popping from an empty stack.

I will use a stack data structure to manage the integers and operations. The main function will parse the input string, split it into tokens, and execute operations based on the token type. Each operation will be implemented as a separate function for clarity.

Here is a breakdown of the operations:
1. **Addition (+)**: Pop the top two elements, add them, and push the result.
2. **Subtraction (-)**: Pop the top two elements, subtract the second from the first, and push the result.
3. **Multiplication (*)**: Similar to addition, but multiply instead.
4. **Division (/)**: Pop two elements, divide the second by the first, and push the result. Handle division by zero.
5. **Swap**: Swap the top two elements.
6. **Dup**: Duplicate the top element.
7. **Pop**: Remove the top element, ensuring the stack is not empty.
8. **Drop**: Remove the top element without returning it.

Here is the Python implementation:
```python
class StackLanguage:
    def __init__(self):
        self.stack = []

def execute(self, command):
        tokens = command.split()
        for token in tokens:
            if token.isdigit():
                self.stack.append(int(token))
            elif token == '+':
                self._add()
            elif token == '-':
                self._subtract()
            elif token == '*':
                self._multiply()
            elif token == '/':
                self._divide()
            elif token == 'swap':
                self._swap()
            elif token == 'dup':
                self._dup()
            elif token == 'pop':
                self._pop()
            elif token == 'drop':
                self._drop()
            else:
                raise ValueError('Invalid operation')

def _add(self):
        self._check_stack(2)
        b = self.stack.pop()
        a = self.stack.pop()
        self.stack.append(a + b)

def _subtract(self):
        self._check_stack(2)
        b = self.stack.pop()
        a = self.stack.pop()
        self.stack.append(a - b)

def _multiply(self):
        self._check_stack(2)
        b = self.stack.pop()
        a = self.stack.pop()
        self.stack.append(a * b)

def _divide(self):
        self._check_stack(2)
        b = self.stack.pop()
        if b == 0:
            raise ZeroDivisionError('Division by zero')
        a = self.stack.pop()
        self.stack.append(a // b)

def _swap(self):
        self._check_stack(2)
        self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]

def _dup(self):
        self._check_stack(1)
        self.stack.append(self.stack[-1])

def _pop(self):
        self._check_stack(1)
        self.stack.pop()

def _drop(self):
        self._check_stack(1)
        self.stack.pop()

def _check_stack(self, size):
        if len(self.stack) < size:
            raise IndexError('Underflow')
```
This code defines a class `StackLanguage` that processes commands and manages a stack.

This implementation is straightforward and works well for small inputs. However, for larger inputs or more complex operations, performance could be improved by optimizing the parsing logic or using a more efficient data structure. Additionally, error handling could be enhanced to provide more informative messages for different types of errors.

Evaluate a Small Stack-Based Integer Language

Retell

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Retell Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string