How to deduce operator precedence from a string input in python?

Question

I am a beginner to Python. I have tried learning python and C++ in the past had learnt about like classes and stuff but then had to abandon it for reasons, now I am learning python from the beginning as I have forgotten it all.

So I was trying to make a calculator like the ones you have in mobile using python but without any GUI. Now, the problem I am having right now is, see in your mobile calculator you can do one operation after the other i.e. say you typed 95+8x2, that mobile calculator will have no problem in deducing operator precedence from your input and give result as 111 and I am trying to do something similar.

But the problem is, the way I know how to do it as a beginner would require a lot of code, it would not be complex but get too long and hence a lot of time wasted. Here is how I have thought of doing it right now :

Find the location of each of the operators in the input for that I am using their indexes i.e. I have named the input as 'alg_operation' and for example, I am using alg_operation.find('*') to where the multiplaction operator is, I am calling this index as location_prod using this I am able to calculate the product simply via converting the part of the string that comes before the operator into float then multiply it with the other part that comes just after (obviously converting it into float as well).

After finding the location of each of the 5 operators that I have decided to include i.e. exponentiation, multiplication, division (// not /), addition and subtraction, I would have to write code for 120 different cases of the arrangement of these operators, which may not be complex but definitely will take a lot of time.

How can I quickly deduce operator precedence from the string input ?

I will update this post if I learn anything new, since I am a beginner to programming.

Answer 1

Converting it to reverse polish notation will solve your problem

def readNumber(string: str,index: int):
    number = ""
    while index < len(string) and isNumber(string[index]):
        number += string[index]
        index += 1
    return float(number), index


def isOperator(token):
    operators = ['+', '-', '*', '/', '%']
    return token in operators

def isNumber(token):
    return (token >= '0' and token <= '9') or token == "."



def toRpn(string: str):
    """
    Converts infix notation to reverse polish notation
    """
    precedence = {
        '(': 0,
        '-': 1,
        '+': 1,
        '*': 2,
        '/': 2,
        '%': 2,
    }

    i = 0
    fin = []
    ops = []

    while i < len(string):
        token = string[i]
        if isNumber(token):
            number, i = readNumber(string,i)
            fin.append(number)
            continue
        if isOperator(token):
            top = ops[-1] if ops else None
            if top is not None and precedence[top] >= precedence[token]:
                fin.append(ops.pop())
            ops.append(token)
            i += 1
            continue
        if token == '(':
            ops.append(token)
            i += 1
            continue
        if token == ')':
            while True:
                operator = ops.pop()
                if operator == '(':
                    break
                fin.append(operator)
                if not ops:
                    break
            i += 1
            continue
        i += 1
    while ops:
        fin.append(ops.pop())
    return fin

def calculate_rpn(rpn: list):
    """
    Calculates the result of an expression in reverse polish notation
    """
    stack = []
    for token in rpn:
        if isOperator(token):
            a = stack.pop()
            b = stack.pop()
            if token == '+':
                stack.append(b + a)
            elif token == '-':
                stack.append(b - a)
            elif token == '*':
                stack.append(b * a)
            elif token == '/':
                stack.append(b / a)
            elif token == '%':
                stack.append(b % a)
        else:
            stack.append(token)
    return stack[0]
        

print ("90165: ", calculate_rpn(toRpn("27+38+81+48*33*53+91*53+82*14+96")))
print ("616222: ", calculate_rpn(toRpn("22*26*53+66*8+7*76*25*44+78+100")))
print (calculate_rpn(toRpn("(22+4)*4")))

My Github

You can easily add more operators and their precedence if you want. You have to modify the precedence array and the isOperator function. Also you should modify the function of the respective operator in the calculate_rpn function.

Answer 2

You can indeed evaluate an arbitrary python expression with eval. Use of eval is a pretty big code smell, because it lets you execute anything, but for completeness it would be done like this:

expr = input("Please, please, please only write maths: ")
print(eval(exp))

note that you could type import shutil; shutil.rmtree("/home") and python would cheerfully run it. So obviously we don't want to do this.

We could try to protect ourselves by sanitising the input. In this case this might actually work, with something like:

safe_chars = (".", "*", "+", "/", "-"," ", *range(10))
if not all(x in safe_chars for x in expr):
    raise ValueError("You tried to enter dangerous data!")

I can't immediately think of any way to do anything dangerous with input consisting only of those chars, but doubtless someone will point it out immediately in the comments [in which case I'll add it here]. More generally, sanitising data like this is hard, because in order to know what's safe you really need to understand the input, by which point you've just written a parser.

Please do note that eval is inherently dangerous. It can be a useful hack for once-off code, although even then... and it is of course useful when you actually want to evaluate python code.