If you have 4+3*2, is there an algorithm to calculate this in one pass?

Question

So I implemented this before in JavaScript as a little practice and was sure I found a Wiki page for an algorithm that both converted a typical infix expression to post fix AND calculated the answer in the same pass

In contrast, I can find this (https://en.wikipedia.org/wiki/Shunting-yard_algorithm), but this only converts the expression to postfix - it doesn't actually calculate the answer too

I'm curious, is there something else I should be searching for instead? I found a Wiki article before and was able to implement a function like which could take in strings like calc("(44 / (7 + 4) * 5 - 17) or whatever and it would spit out the answer...the pseudocode was pretty short (like 20 lines max) and I'm pretty sure all the code was nicely contained in a single loop

If anyone could point me in the right direction to find this algorithm/page, I'd really appreciate it. Thanks

Answer 1

The shunting-yard algorithm as described by Wikipedia can easily be modified to compute the value directly. Having popped an operator off the operator stack and its operands off the operand stack, instead of outputting them, compute the result and push it back to the operand stack. To take your example from the heading:

read 4: push 4 on operand stack
read +: push + on operator stack
read 3: push 3 on operand stack
read *: since * has higher precedence than the + at the top
        of the operator stack, push *
read 2: push 2 to operand stack
END   : pop operator (*), pop two operands (3, 2) push 6
END   : pop operator (+), pop two operands (4, 6), push 10
END   : operator stack is empty, result (10) is at top of operand stack.

Answer 2

Using regular expressions, you can make a recursive function for the 4 basic operators supporting parentheses and operator precedence :

for example:

import re
from itertools import accumulate

def calc(S):
    S = S.replace(" ","")
    if not S: return 0
    levels = [*accumulate((c=="(")-(c==")") for c in S)]
    inner  = max(levels)
    if inner: # process innermost parentheses
        start  = levels.index(inner)
        end    = levels.index(inner-1,start)
        return calc(S[:start]+str(calc(S[start+1:end]))+S[end+1:])
    tokens = re.split(r"(?<!\*|\/)(\+|\-)",S)
    if len(tokens)>1: # additions/subtractions (between operands)
        result,sign = 0,1
        for t in tokens:
            if    t == "+": sign = 1
            elif  t == "-": sign = -1
            else: result += sign*calc(t)
        return result
    tokens = re.split(r"(\*|\/)",S)
    if len(tokens)>1: # multiplications and divisions
        result,op = 1,"*"
        for t in tokens:
            if    t == "*" : op = "*"
            elif  t == "/" : op = "/"
            elif  op == "*": result *= calc(t)
            else: result /= calc(t)
        return result
    return float(S)

output:

print(calc("44 / (7 + 4) * 5 - 17")) # 3.0

This works by recursively substituting operations with their resulting value in the string.

The parentheses grouping are handled first by replacing the innermost group with its resulting value.

When there are no more parentheses, the string is split into additions/subtraction groups and recurses to get the any multiply/divide results between them (thus executing the multiplications/divisions first).

The multiplication/division operations are processed at the next level of recursion

and finally, a string without any operator is treated as a number (float)

Postfix stacking is hidden in the recursion although you could probably track it as you go if you need it.

Answer 3

For a non-recursive solution, you can break down the problem in simpler components:

1. tokenizing expressions into a partial RPN stack for specific operators
2. building the RPN notation by successive refinement (using the tokenizer) until only values and operators remain
3. executing the RPN stack to get the final result

The tokenize() function breaks down an expression into first level tokens for a given set of equal-precedence operators. This returns a mini-RPN stack (only for those operators) with operands being any string between these operators. Tokens that are enclosed in parentheses will be processed on a next refinement pass (i.e. by removing the outermost parentheses)

def tokenize(exp,opers):
    result = []
    token,operator,enclosed,pLevel  = "","",True,0
    for c in exp+opers[0]: # extra operator to force out last operation
        if c in opers and token and pLevel == 0:
            if enclosed: token = token[1:-1] # remove enclosing parentheses
            result.append(token)
            if operator: result.append(operator)
            operator,token,enclosed = c,"",True
        else:
            token  += c
            pLevel += (c=="(")-(c==")")
            if c != ")" and pLevel==0: enclosed = False
    return result

The 'RPN()' function breaks down the whole expression by iteratively refining the tokens in a global RPN stack.

def RPN(S):
    result = [S.replace(" ","").replace("**","^")] # unrefined RPN
    done  = False
    while not done: # iterative refinement loop
        previous = result.copy()
        for opers in (["+","-"],["*","/"],["^"]): # reversed precedence
            result = [token for exp in result for token in tokenize(exp,opers)]
            done = result == previous
            if not done: break # refine more, restart operators
    return result

The 'calc()' function takes the components of the RPN stack and executes each operation in order to obtain the resulting value

def calc(S):
    values = []
    for op in RPN(S): # execute RPN
        if   op == "+": values[-2:] = [values[-2] +  values[-1]]
        elif op == "-": values[-2:] = [values[-2] -  values[-1]]
        elif op == "*": values[-2:] = [values[-2] *  values[-1]]
        elif op == "/": values[-2:] = [values[-2] /  values[-1]]
        elif op == "^": values[-2:] = [values[-2] ** values[-1]]
        else: values.append(float(op))
    return values[0]

output:

print(RPN("44 / (7 + 4) * 5 - 17"))
# ['44', '7', '4', '+', '/', '5', '*', '17', '-']
print(calc("44 / (7 + 4) * 5 - 17"))
# 3.0

note that this simple approach does not support monadic negations such as 2**-3 which you would have to write as 2**(-3)