Инфикс в постфикс, используя стек с Regex

Question

Я пытаюсь выяснить домашнее задание и столкнулся с очень специфической c странной проблемой. По сути, я использую регулярное выражение для извлечения всех операторов и операндов по одному за раз в порядке операций, а затем извлекаю их из стека, печатая их в правильной записи постфикса. В большинстве случаев он работает, однако при запуске unittest он не проходит test_infix14, test_infix_bad_expression и тестирует неверный постфикс. Я могу сказать, что это как-то связано с тем, как + и - выходит из выражения (я думаю), но я понятия не имею, что заставляет его делать это таким образом. Любая помощь приветствуется. Я думал, что у меня все получилось, и я сделал это в пятницу, но этот маленький вопрос занял 2 целых дня: P

''' Main Driver Code '''
import re
import stack

def eval_postfix(postfix):
    ''' Postfix '''
    stac = stack.Stack()
    tokens = re.findall(r'\d+|\+|\-|\*|\/', postfix)
    if len(tokens) == 0:
        raise ValueError
    if len(tokens) < 2:
        return float(tokens[0])
    for toke in tokens:
        if toke.isnumeric():
            stac.push(float(toke))
        else: # t is an operator
            op1 = stac.pop() #operand 1
            op2 = stac.pop() #operand 2
            if toke == '+':
                result = op2 + op1
            elif toke == '-':
                result = op2 - op1
            elif toke == '*':
                result = op2 * op1
            elif toke == '/':
                result = op2 / op1
            stac.push(result)
    return float(stac.pop())

def precedence(top, inputSymbol): # check if top has >= precedence than inputSymbol
    ''' Helper precedence function '''
    if len(re.findall(r'\(|\)|\-|\+|\*|\/', top)) > 0: # if top of stack is an operator
        prec = ['(', '-', '+', '*', '/', ')'] # ascending precedence
        topPrec = prec.index(top)  #e.g.: top == '+', then topPrec == 1
        symbol_input = prec.index(inputSymbol)
        #e.g.: inputSymbol == '/', then symbol_input == 4
        return topPrec >= symbol_input #e.g.: 1 >= 4:  false
    return False

def in2post(infix):
    result = ""
    if infix == [None]:
        raise ValueError
    tokens = re.findall(r'\d+|\(|\)|\+|\-|\*|\/', infix)
    stac = stack.Stack()
    for t in tokens:
        if t == '(':
            stac.push(t)
        elif t.isnumeric():
            result += t + ' '
        elif len(re.findall(r'\+|\-|\*|\/', t)) > 0:
            while stac.size() > 0 and precedence(stac.peek(), t): #and s.peek() != '('
                result += stac.pop() + ' '
            stac.push(t)
        else:
            result += stac.pop() + ' '
            while stac.peek() != '(':
                result += stac.pop() + ' '
            stac.pop()
    while stac.size() > 0:
        if stac.peek() != '(':
            result += stac.pop() + ' '
    return result

def main():
    ''' Main Function '''
    with open("data.txt") as file:
        for line in file.readlines():
            print("infix: %s" % line, end='')
            postfix = in2post(line)
            print("postfix: %s" % postfix)
            answer = eval_postfix(postfix)
            print("answer: %s" % answer)
            print()

if __name__ == '__main__':
    main()

''' stack class '''
class Stack:
    ''' see above doc string '''
    def __init__(self):
        ''' constructor '''
        self.stack_array = []

    def push(self, item):
        ''' add to the stack '''
        self.stack_array.append(item)

    def pop(self):
        ''' remove from the array '''
        #try:
        #    return self.stack_array.pop()
        #except IndexError:
        #    print(self.stack_array)
        if len(self.stack_array) == 0:
            raise IndexError
        return self.stack_array.pop()

    def peek(self):
        ''' See top item of array '''
        #if self.stack_array == [')']:
        #    raise SyntaxError
        if len(self.stack_array) == 0:
            raise IndexError
        return self.stack_array[-1]

    def size(self):
        ''' get total size of array '''
        return len(self.stack_array)

    def clear(self):
        ''' clear whole array '''
        self.stack_array = []

import unittest
from stack import Stack
from main import eval_postfix as epf
from main import in2post as i2p
from main import main as mn
import io
import sys

class TestEvaluation(unittest.TestCase):
    def test_bad_postfix(self):
        self.assertRaises(SyntaxError,  epf, " 7 9 * 7 + 5 6 * - 3 + 4 -+")
        self.assertRaises(ValueError, epf, [None])

class TestIn2Postfix(unittest.TestCase):
    def test_infix_14(self):
        postfix = i2p("7*9+7-5*6+3-4")
        self.assertEqual(postfix.replace(" ", ""), "7 9 * 7 + 5 6 * - 3 + 4 -".replace(" ", ""))
    def test_infix_bad_expression(self):
        self.assertRaises(SyntaxError, i2p, "(8+3)*(5-6))")

class TestMainOutput(unittest.TestCase):
    def test_main_output(self):
        self.maxDiff = None
        captured_output = io.StringIO()
        sys.stdout = captured_output
        mn()
        sys.stdout = sys.__stdout__
        data = "".join(captured_output.getvalue().split())
        print(sys.stdout)
        data1 = "infix: 4postfix:  4answer: 4.0infix: 5  +7postfix:  5 7 +answer: 12.0infix: 7*5postfix:  7 5 *answer: 35.0infix: (5-3)postfix:  5 3 -answer: 2.0infix: 5/5postfix:  5 5 /answer: 1.0infix: 8*5+3postfix:  8 5 * 3 +answer: 43.0infix: 8*(5+3)postfix:  8 5 3 + *answer: 64.0infix: 8+3*5-7postfix:  8 3 5 * + 7 -answer: 16.0infix: (8+3)*(5-6)postfix:  8 3 + 5 6 - *answer: -11.0infix: ((8+3)*(2-7))postfix:  8 3 + 2 7 - *answer: -55.0infix: ((8+3)*2)-7postfix:  8 3 + 2 * 7 -answer: 15.0infix: (8*5)+((3-2)-7*3)postfix:  8 5 * 3 2 - 7 3 * - +answer: 20.0infix: ((8*5+3)-7)-(5*3)postfix:  8 5 * 3 + 7 - 5 3 * -answer: 21.0infix: 7*9+7-5*6+3-4postfix:  7 9 * 7 + 5 6 * - 3 + 4 -answer: 39.0".replace(" ","")
        self.assertEqual(data, data1)

Answer 1

Проблема в вашей функции precedence. Правила для алгоритма Шунтирующий двор гласят:

if the token is an operator, then:
    while ((there is a function at the top of the operator stack)
           or (there is an operator at the top of the operator stack with greater precedence)
           or (the operator at the top of the operator stack has equal precedence and the token is left associative))
          and (the operator at the top of the operator stack is not a left parenthesis):
        pop operators from the operator stack onto the output queue.
    push it onto the operator stack.

Сложение и вычитание (+ и -) имеют равный приоритет, а также умножение и деление (* и /) имеют равный приоритет. Но ваша precedence функция дает + более высокий приоритет, чем -, и * выше, чем /. Это приведет к неверному выводу.

Например, если вам дано выражение инфикса 7-3+4, то после анализа 3 ваш вывод будет 7 3, а стек содержит - , Вы анализируете + и видите, что + имеет более высокий приоритет, чем -, поэтому вы кладете sh в стек операторов. Затем вы анализируете 4 и в итоге получаете 7 3 4. Наконец, вы начинаете выталкивать стек, заканчивая 7 3 4 + 1. Что будет оцениваться как 7 - (3 + 4).

Вы должны изменить свою функцию приоритета так, чтобы - и + имели одинаковый приоритет. И * и / имеют одинаковый приоритет.