Оценить дерево выражений постфикса - Калькулятор - PullRequest
Новая
       53

Оценить дерево выражений постфикса - Калькулятор

2 голосов
/ 26 мая 2020

У меня есть код для генерации постфиксного выражения из инфикса и создания дерева выражения из постфиксной записи. Проблема в том, что если я дам ему выражение типа 45/15 * 3, оно даст мне результат 1 вместо 9, потому что сначала он решает самые глубокие уровни дерева. Могу ли я сделать еще один обход, чтобы правильно оценить выражение? 

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

1 Ответ

1 голос
/ 26 мая 2020

Постфиксное выражение вашего примера 45/15 * 3 будет: 

45 15 / 3 *

Таким образом, сгенерированное дерево будет выглядеть так: 

        * 
   /        3
45   15

Итак, ваш алгоритм обхода кажется правильным, так как это было бы 45/15 = 3, тогда 3 * 3 = 9.

Проблема на самом деле довольно незначительна в вашем генераторе постфиксов. В частности, в функции HasHigherPrecedence вы должны вернуть op1_weight >= op2_weight. Оно должно быть больше или равно, потому что в таких примерах, как этот, где операторы имеют одинаковый приоритет, они должны выполняться в том порядке, в котором они появляются. Так что деление будет выполнено первым.

...