Evaluate Postfix Expression Tree - Calculator

Question

I have code to generate a postfix expression from infix and generate an expression tree from the postfix notation. The problem is, if I give it an expression like 45 / 15 * 3, it will give me the result 1 instead of 9, because it is solving the deepest levels of the tree first. Is there another traversal I can do to evaluate the expression properly?

def evaluate(self):

    if not self.is_empty():
        if not infix_to_postfix.is_operator(self._root):
            return float(self._root)
        else:
            A = self._left.evaluate()
            B = self._right.evaluate()
            if self._root == "+":
                return A + B
            elif self._root == "-":
                return A - B
            elif self._root == "*":
                return A * B
            elif self._root == "/":
                return A / B

def InfixToPostfix(exp: str):
    exp = exp.replace(" ", "")

    S = Stack()
    postfix = ""
    j = 0
    for i in range(len(exp)):
        if is_operand(exp[i]):
            if i + 1 <= len(exp) - 1 and is_operand(exp[i+1]):
                continue
            else:
                j = i
                while j - 1 >= 0 and is_operand(exp[j - 1]):
                    if is_operand(exp[j]):
                        j -= 1
                    else:
                        break
            postfix += exp[j:i + 1] + " "
        elif is_operator(exp[i]):
            while not S.is_empty() and S.top() != "(" and \ HasHigherPrecedence(S.top(), exp[i]):
                if is_operator(S.top()):
                    postfix += S.top() + " "
                else:
                    postfix += S.top()
                S.pop()
            S.push(exp[i])
        elif exp[i] == "(":
            S.push(exp[i])
        elif exp[i] == ")":
            while not S.is_empty() and S.top() != "(":
                if is_operator(S.top()):
                    postfix += S.top() + " "
                else:
                    postfix += S.top()
                S.pop()
        else:
            print("There's an invalid character")
            return

    while not S.is_empty():
        if S.top() == '(':
            S.pop()
            continue
        if is_operator(S.top()):
            postfix += S.top() + " "
        else:
            postfix += S.top()
        S.pop()

    return postfix


def HasHigherPrecedence(op1: str, op2: str):
    op1_weight = get_operator_weight(op1)
    op2_weight = get_operator_weight(op2)
    return op1_weight > op2_weight

Answer 1

The postfix expression of your example 45 / 15 * 3 would be:

45 15 / 3 *

So the tree generated would look like:

        * 
   /        3
45   15

So your traversal algorithm appears correct, as it would do 45 / 15 = 3, then 3 * 3 = 9.

The issue is actually pretty minor in your postfix generator. Specifically, in the function HasHigherPrecedence, you should return op1_weight >= op2_weight. It should be greater than or equal to because in examples such as this one where the operators have the same precedence, they should be executed in the order they appear. So division would be done first.