我正在尝试找出一项家庭作业，并且遇到了一个非常特殊的怪异问题。基本上，我使用正则表达式按操作顺序一次拉出所有运算符和操作数，然后将它们弹出堆栈，同时以正确的后缀表示法打印它们。它在大多数情况下都有效，但是在运行单元测试时，它会导致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)
问题出在您的precedence函数中。 Shunting yard algorithm的规则说：
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。您解析-，您会发现+的优先级高于+，因此将其推入运算符堆栈。然后，您解析-并最终得到4的输出。最后，您开始弹出堆栈，最后以7 3 4结尾。它将评估为7 3 4 + 1。
您必须更改优先级功能，以便7 - (3 + 4)和-具有相同的优先级。并且+和*具有相同的优先级。