使用堆栈 w/Regex 对 Postfix 进行中缀
Infix to Postfix using a stack w/Regex
我正在尝试找出家庭作业，但我 运行 遇到了一个非常具体的奇怪问题。基本上，我使用正则表达式按操作顺序一次将所有运算符和操作数拉出，然后将它们从堆栈中弹出，同时以正确的后缀表示法打印它们。它在大多数情况下都有效，但是当 运行 进行单元测试时，它会失败 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).
您必须更改优先级函数，使 - 和 + 具有相同的优先级。 * 和 / 具有相同的优先级。
我正在尝试找出家庭作业，但我 运行 遇到了一个非常具体的奇怪问题。基本上，我使用正则表达式按操作顺序一次将所有运算符和操作数拉出，然后将它们从堆栈中弹出，同时以正确的后缀表示法打印它们。它在大多数情况下都有效，但是当 运行 进行单元测试时，它会失败 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).
您必须更改优先级函数，使 - 和 + 具有相同的优先级。 * 和 / 具有相同的优先级。