11
\$\begingroup\$

I've recently been assigned an assignment to create a word calculator, and given my knowledge in python is still quite lacking, I want to ask if anybody has any better ideas for any possible solutions.

The question is here:

Jimmy has invented a new kind of calculator that works with words
rather than numbers.

  • Input is read from stdin and consists of up to 1000 commands, one per line.

  • Each command is a definition, a calculation or clear.

  • All tokens within a command are separated by single spaces.

  • A definition has the format def x y where x is a variable name and y is an integer in the range [-1000, 1000].

  • Existing definitions are replaced by new ones i.e. if x has been defined previously, defining x again erases its old definition.

  • Variable names consist of 1-30 lowercase characters.

  • No two variables are ever defined to have the same value at the same time.

  • The clear command erases all existing variable definitions.

  • A calculation command starts with the word calc, and is followed by one or more variable names separated by addition or subtraction operators.

  • The end of a calculation command is an equals sign.

The goal is to write a program for Jimmy's calculator. Some rules are:

  • The program should produce no output for definitions, but for calculations it should output the value of the calculation.
  • Where there is no word for the result, or some word in a calculation has not been defined, then the output should be unknown. (The word unknown is never used as a variable name.)
  • Your solution may only import content from the sys module.
  • Your solution may not use the eval() function.

Here is a sample input below:

calc foo + bar =
def bar 7
def programming 10
calc foo + bar =
def is 4
def fun 8
calc programming - is + fun =
def fun 1
calc programming - is + fun =
clear

And the corresponding output:

foo + bar = unknown
foo + bar = programming
programming - is + fun = unknown
programming - is + fun = bar

My current solution is this:

import sys
lines = sys.stdin.readlines()

d_define = {}
numsInDict = []
operators = ["+", "-", "="]

# IN : word to checked it is in the dictionary
# OUT : returns unknown or value for word
def lookup(word):
    if word in d_define:
        return d_define[word]
    else:
        return "unknown"

# IN : answer to check if there is a word assigned to it a dictionary
# OUT : returns unknown or word assigned to answer
def getAnswer(answer):
    for k, v in d_define.items():
        if v == answer:
            return k
    return "unknown"

# IN : All values to calc (includes operators)
# OUT : print unknown or word if in dict
def calc(args):
    equation = 0
    lastOperator = "+"
    for word in args:
        if word not in operators:
            res = lookup(word)
            if res == "unknown":
                return "unknown"
            else:
                #print(res)
                if lastOperator == "+":
                    equation += res
                else:
                    equation -= res
        else:
            lastOperator = word
    if equation in numsInDict:
        res = getAnswer(equation)
        return res
    else:
        return "unknown"

# IN : word to be added and its value
# OUT : updated dictionary
def define(word, num):
    num = int(num)
    if num in numsInDict or word in d_define:
        # print(f'NEEDS REPLACE')
        # print(f'same value -> {num in numsInDict}')
        # print(f'same word -> {word in d_define}')
        # print(f'same word -> {d_define}')
        # print(f'same word -> {numsInDict}')
        topop = ""
        for k, v in d_define.items():
            if k == word:
                d_define[word] = num  # Update Word with new value
            elif v == num:
                topop = k  # Saves value to pop later
        if topop != "":
            d_define.pop(topop)
            d_define[word] = num
    else:
        d_define[word] = num
        numsInDict.append(num)
    #print(f'{word} - {d_define[word]}')

for line in lines:
    #print(f'-------------------------------------- LOOP START ------------------------------------')
    line = line.rstrip().split()
    #print(f'Line Split - {line}')
    if len(line) == 3 and line[0] == "def":
        define(line[1], line[2])
    elif len(line) > 1 and line[len(line) - 1] == "=":
        result = calc(line[1:])
        print(f'{" ".join(line[1:]) + " " + result}')
    elif len(line) == 1 and line[0] == "clear":
        d_define = {}
        wordsInDict = []
        numsInDict = []
        #print(f'Cleared d_define - {d_define} {wordsInDict}')
    #print(d_define)
    #print(f'--------------------------------------- LOOP END -------------------------------------')

It does feel quite clunky but it gets the job done. I am just wondering if anybody has any better ways in which it could be improved upon.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ There's at least one reference to this online, at Chegg. What is the original source? \$\endgroup\$
    – Reinderien
    Mar 11 at 23:25
  • \$\begingroup\$ It feels a bit odd that an unparseable line doesn't throw an error \$\endgroup\$ Mar 12 at 22:04

2 Answers 2

8
\$\begingroup\$

I think your solution does work, but it's very long-winded. Your IN: and OUT: comments should be moved to docstrings """ """ in the first line of the function body.

getAnswer should be get_answer by PEP8.

Your getAnswer doesn't need to loop if you maintain an inverse dictionary of values to names.

Consider using the built-in operator.add and .sub. This violates the letter (though perhaps not the spirit) of Your solution may only import content from the sys module; if that's actually a problem just define the add and sub functions yourself.

You should just delete your LOOP START and LOOP END comments.

Consider writing unit tests to validate your output. This can be done by operating on the stdin and stdout streams passed as parameters, or yielding lines.

Suggested

from operator import add, sub
from typing import Iterable, Iterator


def rewritten(in_stream: Iterable[str]) -> Iterator[str]:
    OPS = {'+': add, '-': sub}
    state, inverse_state = {}, {}

    for line in in_stream:
        command, *args = line.split()

        if command == 'def':
            name, val = args
            val = int(val)
            state[name] = val
            inverse_state[val] = name

        elif command == 'clear':
            state.clear()
            inverse_state.clear()

        elif command == 'calc':
            result, *values = (state.get(name) for name in args[::2])

            if result is not None:
                for op, value in zip(args[1:-1:2], values):
                    if value is None:
                        result = None
                        break
                    result = OPS[op](result, value)

            prefix = line.rstrip().split(maxsplit=1)[1]
            result = inverse_state.get(result, 'unknown')
            yield f'{prefix} {result}'


def test() -> None:
    sample_in = (
'''def foo 3
calc foo + bar =
def bar 7
def programming 10
calc foo + bar =
def is 4
def fun 8
calc programming - is + fun =
def fun 1
calc programming - is + fun =
clear'''
    ).splitlines()

    actual = '\n'.join(rewritten(sample_in))

    assert actual == (
'''foo + bar = unknown
foo + bar = programming
programming - is + fun = unknown
programming - is + fun = bar'''
    )


if __name__ == '__main__':
    test()

Even more lookups

As @Stef suggests, it is possible to add a lookup for the command. It's awkward, because only one of the three functions actually produces a result. One way to express this is an unconditional outer yield from, and all functions as generators, only one being non-empty. I don't particularly recommend this; it's just a demonstration:

def rewritten(in_stream: Iterable[str]) -> Iterator[str]:
    def clear() -> Iterator[str]:
        state.clear()
        inverse_state.clear()
        return; yield

    def define(name: str, val: str) -> Iterator[str]:
        val = int(val)
        state[name] = val
        inverse_state[val] = name
        return; yield

    def calc(*args: str) -> Iterator[str]:
        result, *values = (state.get(name) for name in args[::2])

        if result is not None:
            for op, value in zip(args[1:-1:2], values):
                if value is None:
                    result = None
                    break
                result = OPS[op](result, value)

        prefix = line.rstrip().split(maxsplit=1)[1]
        result = inverse_state.get(result, 'unknown')
        yield f'{prefix} {result}'

    OPS = {'+': add, '-': sub}
    COMMANDS = {'clear': clear, 'def': define, 'calc': calc}
    state, inverse_state = {}, {}

    for line in in_stream:
        parts = line.split()
        command, *args = parts
        yield from COMMANDS[command](*args)

Or just use Optionals:

def rewritten(in_stream: Iterable[str]) -> Iterator[str]:
    def clear() -> Optional[str]:
        state.clear()
        inverse_state.clear()

    def define(name: str, val: str) -> Optional[str]:
        val = int(val)
        state[name] = val
        inverse_state[val] = name

    def calc(*args: str) -> Optional[str]:
        result, *values = (state.get(name) for name in args[::2])

        if result is not None:
            for op, value in zip(args[1:-1:2], values):
                if value is None:
                    result = None
                    break
                result = OPS[op](result, value)

        prefix = line.rstrip().split(maxsplit=1)[1]
        result = inverse_state.get(result, 'unknown')
        return f'{prefix} {result}'

    OPS = {'+': add, '-': sub}
    COMMANDS = {'clear': clear, 'def': define, 'calc': calc}
    state, inverse_state = {}, {}

    for line in in_stream:
        parts = line.split()
        command, *args = parts
        result = COMMANDS[command](*args)
        if result is not None:
            yield result
\$\endgroup\$
2
  • \$\begingroup\$ You suggest using a dictionary to map operator symbols to the corresponding operations, OPS = {'+': add, '-': sub}. I think that's a great idea. You could also use a dictionary to map commands clear, def, calc to functions. This way, you could encapsulate the code of the commands in functions, and avoid bogging the main loop of function rewritten with a huge if/elif/else. \$\endgroup\$
    – Stef
    Mar 12 at 13:41
  • \$\begingroup\$ @Stef I hesitate to think that a ~20-line if/elif is "huge". If it were larger I would agree. \$\endgroup\$
    – Reinderien
    Mar 12 at 16:52
5
\$\begingroup\$

The reason your solution is convoluted is that the problem hamstringing you by not allowing any modules (except sys) including the built in ones!

Secondly it seems you need to freshen up on your basics. For instance this

def lookup(word):
    if word in d_define:
        return d_define[word]
    else:
        return "unknown"

Can be written as

d_define.get(word, "unknown")

Secondly d_define is a bad name; as a general rule avoid abbreviations in variable and function names. Assume that everything is fair game, no limitations on external libraries. The crux is that eval is really dangerous, and you should never run it on user input. For instance an user could import the os library and then run commands to delete your whole file system. However, there are safe ways to use it, for instance

    SAFE_CHARS = set("0123456789+-*(). /")

    for char in expr:
        if char not in SAFE_CHARS:
            value = "unknown"
            break
    else:
        value = eval(expr)

If we detect any "malicious intent", e.g anything other that mathematical expressions we break and return "unknown". We first replace all the words with their values before evaluating. Some care is taken here for instance if we have "foobar=3" and "bar=2" then "foobar" must be replaced before "bar" otherwise we might end up with "foo2".

Note that this way of solving the problem is very slow with many definitions, but I really do not think speed matters.

import sys


SAFE_CHARS = set("0123456789+-*(). /")


class Calculator:
    def __init__(self):
        self.definitions = dict()
        self.values = dict()

    def definition(self, name: str, integer: float) -> None:
        self.definitions[name] = integer
        self.values[integer] = name

    def clear(self):
        self.definitions = dict()
        self.values = dict()

    def calculate(self, expr: str) -> float | str:
        expr = "".join(expr.split())  # Remove all spaces
        definitions = sorted(
            self.definitions.items(), key=lambda x: len(x[0]), reverse=True
        )

        for (word, value) in definitions:
            expr = expr.replace(word, str(value))

        if all(c in SAFE_CHARS for c in char):
            value = eval(expr)
        else:
            value = "unknown"

        return self.values.get(value, "unknown")


if __name__ == "__main__":

    calc = Calculator()
    for line in sys.stdin.readlines():
        if not (line := line.strip()):
            continue
        if line.startswith("def"):
            _, name, value = line.split()
            calc.definition(name, float(value))
        elif line.startswith("calc") and line.endswith("="):
            _, expr = line[:-1].split("calc")
            print(f"{line} {calc.calculate(expr)}")
        elif line.startswith("clear"):
            calc.clear()

Assuming that eval is off the table, I would probably rewrite it as follows. Due note that we use a recursive algorithm just for fun to evaluate the expressions. A lot of care is taken to correctly handle deeply nested expressions.

import sys


def is_number(s: str) -> bool:
    try:
        float(s)
        return True
    except ValueError:
        return False


class Calculator:
    def __init__(self):
        self.definitions = dict()
        self.values = dict()

    def definition(self, name: str, integer: float) -> None:
        self.definitions[name] = integer
        self.values[integer] = name

    def clear(self):
        self.definitions = dict()
        self.values = dict()

    def calculate(self, expr: str) -> float | str:
        expr = "".join(expr.split())  # Remove all spaces
        try:
            value = self._eval(expr)
        except KeyError:
            value = "unknown"
        return self.values.get(value, "unknown")

    def _eval(self, expr: str) -> float:
        """self.evaluates an expression consisting of binary expressions

        >>> calculator._eval("123.5")
        123.5
        >>> calculator._eval("(5 + 3) + (1 + (2 + 6))")
        17.0
        >>> calculator._eval("((((5))+(2))+1+2)")
        10.0
        """
        if is_number(expr):
            return float(expr)
        if "(" in expr:
            start, stop = inner_expression(expr)
            new_expr = self._eval(expr[start + 1 : stop - 1])
            expr = expr.replace(expr[start:stop], str(new_expr))
            return self._eval(expr)
        elif "+" in expr:
            expr_1, expr_2 = expr.split("+", 1)
            return self._eval(expr_1) + self._eval(expr_2)
        elif "-" in expr:
            expr_1, expr_2 = expr.split("-", 1)
            return self._eval(expr_1) - self._eval(expr_2)
        elif "/" in expr:
            expr_1, expr_2 = expr.split("/", 1)
            return self._eval(expr_1) / self._eval(expr_2)
        elif "*" in expr:
            expr_1, expr_2 = expr.split("*", 1)
            return self._eval(expr_1) * self._eval(expr_2)
        elif "^" in expr:
            expr_1, expr_2 = expr.split("^", 1)
            return self._eval(expr_1) ** self._eval(expr_2)
        return self.definitions[expr]


MATCHING_BRACKET = {")": "(", "}": "{", "[": "]"}
OPEN_BRACKETS = set(["(", "{", "["])


def inner_expression(expr: str):
    """Returns the indices for the inner most expression

    >>> inner_expression("(5}")
    Traceback (most recent call last):
    ValueError: Incompatible brackets '}' does not match '('!

    >>> inner_expression("((5)")
    Traceback (most recent call last):
    ValueError: Incomplete brackets found, the brackets ['('] was never closed!

    >>> a, b = inner_expression('((5+2)+(1+2))'); '((5+2)+(1+2))'[a:b]
    '(5+2)'

    >>> a, b = inner_expression('((((5))+(2))+1+2)'); '((((5))+(2))+1+2)'[a:b]
    '(5)'
    """
    stack = []
    deepest_nesting = start = 0
    indices = None
    for i, char in enumerate(expr):
        if char in MATCHING_BRACKET:
            if stack[-1] != MATCHING_BRACKET[char]:
                raise ValueError(
                    f"Incompatible brackets '{char}' does not match '{stack[-1]}'!"
                )
            if (nesting := len(stack)) > deepest_nesting:
                deepest_nesting = nesting
                indices = (start, i + 1)
            stack.pop()
        elif char in OPEN_BRACKETS:
            stack.append(char)
            start = i
    if stack:
        raise ValueError(
            f"Incomplete brackets found, the brackets {stack} was never closed!"
        )
    return indices if indices is not None else (0, len(expr))


if __name__ == "__main__":
    import doctest

    doctest.testmod(extraglobs={"calculator": Calculator()})

    calc = Calculator()
    for line in sys.stdin.readlines():
        if not (line := line.strip()):
            continue
        if line.startswith("def"):
            _, name, value = line.split()
            calc.definition(name, float(value))
        elif line.startswith("calc") and line.endswith("="):
            _, expr = line[:-1].split("calc")
            print(f"{line} {calc.calculate(expr)}")
        elif line.startswith("clear"):
            calc.clear()

EDIT: If we allow ourselves to use the full capabilities of Python, disregarding that our code must be beginner friendly we can do as shown below

  • Reduce was introduced to reduce the number of recursive calls and offer a small speed improvement. Our original code reduced the expression as follows a + b + c + d + e = a + (b + c + d+ e) = a a + (b + (c + d + e)) usw.

  • The operators were extracted into a seperate function reducing this

          elif "+" in expr:
              expr_1, expr_2 = expr.split("+", 1)
              return self._eval(expr_1) + self._eval(expr_2)
          elif "-" in expr:
              expr_1, expr_2 = expr.split("-", 1)
              return self._eval(expr_1) - self._eval(expr_2)
          elif "/" in expr:
              expr_1, expr_2 = expr.split("/", 1)
              return self._eval(expr_1) / self._eval(expr_2)
          elif "*" in expr:
              expr_1, expr_2 = expr.split("*", 1)
              return self._eval(expr_1) * self._eval(expr_2)
          elif "^" in expr:
              expr_1, expr_2 = expr.split("^", 1)
              return self._eval(expr_1) ** self._eval(expr_2)
          return self.definitions[expr]
    

    into this

      for operator, function in OPERATORS.items():
          if operator not in expr:
              continue
          expressions = map(self._eval, expr.split(operator))
          return reduce(function, expressions)
    
  • Minor cleanup for the inner_expression as well

  • A bit more typing hints and doctests

Code without imports

import sys


def is_number(s: str) -> bool:
    try:
        float(s)
        return True
    except ValueError:
        return False


OPERATORS = {
    "+": lambda x, y: x + y,
    "-": lambda x, y: x - y,
    "/": lambda x, y: x / y,
    "*": lambda x, y: x * y,
    "^": lambda x, y: x**y,
}


def reduce(function, iterable, initializer=None):
    """Implements the reduce function without external modules

    >>> reduce(lambda x, y: x + y, range(5))
    10
    >>> reduce(lambda x, y: x + y, range(5), initializer=100)
    110
    >>> reduce(lambda x, y: f"({x}) + {y}", range(5))
    '((((0) + 1) + 2) + 3) + 4'
    >>> reduce(lambda x, y: f"({x}) + {y}", range(5), initializer=100)
    '(((((100) + 0) + 1) + 2) + 3) + 4'
    """
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value


class Calculator:
    def __init__(self) -> None:
        self.definitions = dict()
        self.values = dict()

    def definition(self, name: str, integer: float) -> None:
        self.definitions[name] = integer
        self.values[integer] = name

    def clear(self) -> None:
        self.definitions = dict()
        self.values = dict()

    def calculate(self, expr: str) -> float | str:
        expr = "".join(expr.split())  # Remove all spaces
        try:
            value = self._eval(expr)
        except KeyError:
            value = "unknown"
        return self.values.get(value, "unknown")

    def _eval(self, expr: str) -> float:
        """self.evaluates an expression consisting of binary expressions

        >>> qalc._eval("123.5")
        123.5
        >>> qalc._eval("(5 + 3) + (1 + (2 + 6))")
        17.0
        >>> qalc._eval("((((5))+(2))+1+2)")
        10.0
        """
        if is_number(expr):
            return float(expr)

        if "(" in expr:
            start, stop = inner_expression(expr)
            new_expr = self._eval(expr[start + 1 : stop - 1])
            expr = expr.replace(expr[start:stop], str(new_expr))
            return self._eval(expr)

        for operator, function in OPERATORS.items():
            if operator not in expr:
                continue
            expressions = map(self._eval, expr.split(operator))
            return reduce(function, expressions)

        return self.definitions[expr]


MATCHING_BRACKET = {")": "(", "}": "{", "[": "]"}
OPEN_BRACKETS = set(["(", "{", "["])


def inner_expression(expr: str) -> tuple[int, int]:
    """Returns the indices for the inner most expression

    >>> inner_expression("(5}")
    Traceback (most recent call last):
    ValueError: Incompatible brackets '}' does not match '('!
    >>> inner_expression("((5)")
    Traceback (most recent call last):
    ValueError: Incomplete brackets found, the brackets ['('] was never closed!
    >>> a, b = inner_expression('((5+2)+(1+2))'); '((5+2)+(1+2))'[a:b]
    '(5+2)'
    >>> a, b = inner_expression('((((5))+(2))+1+2)'); '((((5))+(2))+1+2)'[a:b]
    '(5)'
    """
    stack = []
    deepest_nesting = start = 0
    indices = None
    for i, char in enumerate(expr):

        if char in OPEN_BRACKETS:
            stack.append(char)
            start = i
            continue
        elif char not in MATCHING_BRACKET:
            continue

        matching_brackets = stack[-1] == MATCHING_BRACKET[char]

        if not matching_brackets:
            raise ValueError(
                f"Incompatible brackets '{char}' does not match '{stack[-1]}'!"
            )

        if (nesting := len(stack)) > deepest_nesting:
            deepest_nesting = nesting
            indices = (start, i + 1)
        stack.pop()

    if stack:
        raise ValueError(
            f"Incomplete brackets found, the brackets {stack} was never closed!"
        )

    if indices is None:
        return (0, len(expr))
    return indices


def first_and_remaining(line: str) -> tuple[str, str | None]:
    """If lines = 'a b c' this returns ('a', 'b c')

    >>> first_and_remaining('a b c')
    ('a', 'b c')
    >>> first_and_remaining('')
    ('', None)
    >>> first_and_remaining(' a ')
    ('a', None)
    >>> first_and_remaining(' a b ')
    ('a', 'b')
    """
    if " " not in (stripped := line.strip()):
        return stripped, None
    return tuple(x.strip() for x in stripped.split(maxsplit=1))


def calculator(lines, calc=None) -> None:
    """Feeds lines into a calculator

    >>> commands = '''
    ... def foo 3
    ... calc foo + bar =
    ... def bar 7
    ... def programming 10
    ... calc foo + bar =
    ... def is 4
    ... def fun 8
    ... calc programming - is + fun =
    ... def fun 1
    ... calc programming - is + fun =
    ... clear'''
    >>> calculator(commands.splitlines())
    calc foo + bar = unknown
    calc foo + bar = programming
    calc programming - is + fun = unknown
    calc programming - is + fun = bar
    """
    if calc is None:
        calc = Calculator()

    for command, expression in map(first_and_remaining, lines):

        if not command:
            continue

        if expression is None:
            if command == "clear":
                calc.clear()
            continue

        if command == "def":
            name, value = expression.split()
            calc.definition(name, int(value))

        elif command == "calc" and expression.endswith("="):
            value = calc.calculate(expression[:-1])
            print(f"{command} {expression} {value}")


if __name__ == "__main__":
    import doctest

    doctest.testmod(extraglobs={"qalc": Calculator()})

    calculator(sys.stdin.readlines())
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.