使用堆栈计算后缀

Question

我的任务是转换一个完全加括号的中缀表达式。示例

(((54 + 56) + (73) 4 +) + (9 + 7))

后缀。然后对后缀求值。表达式是用户输入的。我必须使用已经为我编写的Stack类。不能修改:

class Stack:
    def __init__(self):
        self.theStack=[]
    def top(self):
        if self.isEmpty():
            return "Empty Stack"
        else:
            return self.theStack[-1]
    def isEmpty(self):
        return len(self.theStack)==0
    def push(self,item):
        self.theStack.append(item)
    def pop(self):
        if not self.isEmpty():
            temp=self.theStack[-1]
            del(self.theStack[-1])
            return temp
        else:
            return "Empty Stack"

我遇到的第一个问题是，当用户输入例如54时，在使用stack时，5和4是两个不同的元素。我怎样才能把它变成一个?

下面是目前为止我计算后缀的代码:

OPERATOR=["+","-","*", "/"]
def evaluatePostfix(Postfix):
    eStack=Stack()
    for n in Postfix:
        if n not in OPERATOR and n!="(" and n!=")":
            eStack.push(n)
        if n in OPERATOR:
            math=eStack.pop()+n+eStack.pop()
            eval(math)

我知道问题出在倒数第二行，但我不确定如何修复

Answer 1

您问了几个问题(您的答案并不完整，因为您的最终目标是求值后缀表达式)，但是让我来解决您问的问题:

"我遇到的第一个问题是，当用户输入例如54时，在使用stack时，5和4是两个不同的元素。我怎样才能把它变成一个?"

如果您决定一次扫描输入的一个字符，那么最简单的方法是使用临时变量。下面是一种用Python快速而简单的方法。

infix = "54 + 490"
postfix = ""
a_number = None
OPERATOR = ["+", "-", "*", "/"]
for n in infix:
    if n not in OPERATOR and n != "(" and n != ")":
        if a_number is None:
            a_number = n
        else:
            a_number = a_number + n
    if n is ")" or n in OPERATOR:
         if a_number is not None:
             postfix += a_number
             a_number = None

if a_number is not None:
    postfix += a_number
    a_number = None
print postfix

Answer 2

当你写:

for n in Postfix

是对后缀中的字符一次迭代一个。最好将Postfix转换为字符串列表，并在下面几行使用辅助函数填充未填充的

操作符。

def foo(str):
 newstr = ""
 for x in str:
  if x not in "0123456789. ":
   newstr += " " + x + " "
  else:
   newstr += x
 return newstr

现在你可以修改

for n in Postfix

for n in foo(Postfix).split()

，它应该解决不能正确处理数字的问题。

split()将字符串分割成非空白字符串的列表，例如:"hello world"将变成["hello"， "world"]