修改一段代码以允许浮点数和负数以及输入字符串中字符之间的任意数量的空格
Modify piece of code to allow floats and negative numbers as well as an arbitrary amount of spaces in between the characters in the inputted string
以下代码获取中缀字符串并将其转换为后缀并将新表达式作为字符串输出。但是它不支持负数或浮点数。以下代码仅允许单个数字值：
例如 (0-9) 不像 10 或 11。否则它会抛出 "key error"。另外，如果我添加一个负号，它也会抛出一个关键错误。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def isNumber(self, txt):
if not isinstance(txt,str) or len(txt.strip())==0:
print("Argument error in isNumber")
return False
# YOUR CODE STARTS HERE
try:
float(txt)
return True
except ValueError:
return False
#########################################################################################################
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 4
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split()
for token in tokenList:
if token in "0123456789":
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
所以这是我的修复方法，也允许浮动：
我添加了这个功能：
def isNumber(x):
try:
float(x)
return True
except ValueError:
return False
并将这一行：if token in "0123456789": 更改为：if Stack.isNumber(token):
现在代码允许浮动。
那么另一个问题是什么？好吧，另一个问题是我的代码假设输入字符串在每个字符之间只有一个 space，因此我 string.split() 将所有字符放入列表中。除了输入字符串在字符之间可以有任意数量的 spaces 之外，如果没有 spaces，我的代码会将类似“（（”的内容与我的字符列表进行比较，而不是找到它并抛出 Key error。所以因为我必须允许负数（用减号表示）。我如何修改我的代码，以便它不再抛出 keyerror 并允许我使用负数？
当我这样做时：
print(Stack.infixToPostfix("( ( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"))
我的代码输出如下：
1 3 + 4 * 9.2 0 - 5 8 + * -
效果很好，但是如果我删除一个 space:
"(( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"
我的代码不再有效。 键错误'(('我知道为什么会抛出这个错误（上面的解释），但我不确定如何修复它。
最后一个问题TL:DR
如何修改我的 infixtopostfix 代码以允许字符之间任意数量的 spaces 并允许负数？
首先创建一个单独的函数，它将根据您的字符串生成一个标记列表。标记是数字（没有符号）或单个字符：
def tokenize(s):
s = re.sub(r"\s+", "", s)
result = []
while (s):
if s[0] in "0123456789":
number = s[0]
s = s[1:]
while (s and s[0] in "0123456789."):
number += s[0]
s = s[1:]
result.append(number)
if s:
result.append(s[0])
s = s[1:]
else:
result.append(s[0])
s = s[1:]
return result
然后您需要跟踪一元加减运算。为此，我们引入了一个特殊的 'neg' 操作 - 当您以 postfix 表示法处理此操作时，您只需取反操作数堆栈顶部的值。
您希望在字符串的开头或紧跟在开始的“(”之后进行一元加减运算。在处理数字操作数或结束“)”之后，您将一元标志重置为 False，因为一元加或减号不能出现在这些位置。当一元标志为真时，您必须继续跟踪传入的“+”和“-”，为此使用布尔标志 'neg'。在每个 '-' 处更改 'neg' 状态。当你最终找到一个操作数时——检查 'neg' 标志的状态。如果为 True，则需要将我们特殊的 'neg' 操作放在操作数之后。在结束 ')' 之后放置一个 'neg' 操作有点棘手，需要使用 opStack。
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 3
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
prec["neg"] = 1
opStack = Stack()
postfixList = []
tokenList = tokenize(infixexpr)
print(tokenList)
unary = True
neg = False
for token in tokenList:
if unary and token in "+-":
if token == '-':
neg = not neg
elif isNumber(token):
postfixList.append(token)
if neg:
postfixList.append("neg")
neg = False
unary = False
elif token == '(':
if neg:
opStack.push("neg")
neg = False
opStack.push(token)
unary = True
elif token == ')':
topToken = opStack.pop()
unary = False
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
if not opStack.isEmpty() and opStack.peek() == "neg":
postfixList.append(opStack.pop())
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
输入：
"-(( 1 + 3 ) ) * 4 - ( -9.2 - 0 ) * ( 5 + 8 ) - 4 * (-2)"
输出：
1 3 + neg 4 * 9.2 neg 0 - 5 8 + * - 4 2 neg * -
更新 2020-03-12
如果您想将负数作为单个负操作数处理，而不是像正操作数后跟 'neg' 操作一样，那么您只需要对 infixToPostfix 方法进行非常小的修改。你只需要修改 elif isNumber(token) 分支。不过，我会把它完整地放在这里：
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 3
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
prec["neg"] = 1
opStack = Stack()
postfixList = []
tokenList = tokenize(infixexpr)
unary = True
neg = False
for token in tokenList:
if unary and token in "+-":
if token == '-':
neg = not neg
elif isNumber(token):
if neg:
postfixList.append("-" + token)
else:
postfixList.append(token)
neg = False
unary = False
elif token == '(':
if neg:
opStack.push("neg")
neg = False
opStack.push(token)
unary = True
elif token == ')':
topToken = opStack.pop()
unary = False
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
if not opStack.isEmpty() and opStack.peek() == "neg":
postfixList.append(opStack.pop())
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
现在输出是
1 3 + neg 4 * -9.2 0 - 5 8 + * - 4 -2 * -
更新 2020-03-13
原文中post我放了下面这句话：
You expect unary plus and minus operations at the start of the string or right after the opening '('.
那里和之前更新中的代码也反映了这一点。我知道这在技术上并不完全正确。操作后也可以预期一元操作。但是，我不想允许像 2+--+-+3 这样的表达式，所以我排除了在操作后进行一元操作的可能性。不幸的是，它也排除了 2^-3 的可能性。如果你希望能够解析像 2^-3 这样的表达式，那么你只需要在另一个操作之后允许一元操作，它需要在 else 分支中添加一行 unary = True ：
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
unary = True # This is the only new line
现在您可以将 2^-3 解析为 2^(-3)。但是，它也允许将 2+-3 解析为 2+(-3)。我总是发现最后一种可能性在计算机语言中非常丑陋，但如果它适合你 - 很好。当然，你也可以只允许在^之后解析一元运算，其他运算之后不解析。
这将需要检查当前标记，并且仅当标记在允许其后一元减号的操作列表中时才将 unary 设置为 True 。
您可以使用 try-except 简单地测试整数或浮点数，这也可以处理负数。问题是在 spaces 上拆分比实际解析令牌要灵活和可靠得多，而且它给使用该函数的人带来了巨大的负担。
您需要分词器功能。幸运的是，python 有一个 tokenizer 模块，尽管第一次使用它并不是那么容易。或者您可以自己编写。
这是使用库的快速实现
from io import StringIO
from tokenize import generate_tokens, NUMBER, OP
def tokenizer(s):
generator = generate_tokens(StringIO(s).readline)
for toknum, tokval, _, _, _ in generator:
if toknum in (NUMBER, OP):
yield tokval
只需更改您的代码即可使用
for token in tokenizer(infixexpr):
修复了更长的数字和十进制数字，并在删除所有 space 的情况下处理您的测试用例：
print (infixToPostfix("((1+3))*4-(9.2-0)*(5+8)"))
1 3 + 4 * 9.2 0 - 5 8 + * -
（我认为这应该是一个独立函数，而不是 class 成员。您可能希望通过取消缩进函数来实现它。）
负数需要多一点，因为分词器会立即 return "-" 作为运算符。您可以编写自己的 tokenizer 函数，将 -55 读取为一个标记，或者您可以跟踪状态并意识到如果您不需要运算符，则减号必须表示下一个标记是负数.参见 How to differentiate '-' operator from a negative number for a tokenizer
除了您询问的问题之外，还有一个问题是一元运算符。如果在表达式前允许使用减号，则必须将其作为运算符处理。亚历克斯在另一个答案中处理了它们，您可以查看 Infix to postfix algorithm that takes care of unary operators 一些实现在后缀中将负数打印为“(-5)”。有些人使用 spaces，尽管如果你没有 spaces 它可以节省 space —— 反正它不是真正的人类可读的。
以下代码获取中缀字符串并将其转换为后缀并将新表达式作为字符串输出。但是它不支持负数或浮点数。以下代码仅允许单个数字值：
例如 (0-9) 不像 10 或 11。否则它会抛出 "key error"。另外，如果我添加一个负号，它也会抛出一个关键错误。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def isNumber(self, txt):
if not isinstance(txt,str) or len(txt.strip())==0:
print("Argument error in isNumber")
return False
# YOUR CODE STARTS HERE
try:
float(txt)
return True
except ValueError:
return False
#########################################################################################################
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 4
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split()
for token in tokenList:
if token in "0123456789":
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
所以这是我的修复方法，也允许浮动：
我添加了这个功能：
def isNumber(x):
try:
float(x)
return True
except ValueError:
return False
并将这一行：if token in "0123456789": 更改为：if Stack.isNumber(token):
现在代码允许浮动。
那么另一个问题是什么？好吧，另一个问题是我的代码假设输入字符串在每个字符之间只有一个 space，因此我 string.split() 将所有字符放入列表中。除了输入字符串在字符之间可以有任意数量的 spaces 之外，如果没有 spaces，我的代码会将类似“（（”的内容与我的字符列表进行比较，而不是找到它并抛出 Key error。所以因为我必须允许负数（用减号表示）。我如何修改我的代码，以便它不再抛出 keyerror 并允许我使用负数？
当我这样做时：
print(Stack.infixToPostfix("( ( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"))
我的代码输出如下：
1 3 + 4 * 9.2 0 - 5 8 + * -
效果很好，但是如果我删除一个 space:
"(( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"
我的代码不再有效。 键错误'(('我知道为什么会抛出这个错误（上面的解释），但我不确定如何修复它。
最后一个问题TL:DR
如何修改我的 infixtopostfix 代码以允许字符之间任意数量的 spaces 并允许负数？
首先创建一个单独的函数，它将根据您的字符串生成一个标记列表。标记是数字（没有符号）或单个字符：
def tokenize(s):
s = re.sub(r"\s+", "", s)
result = []
while (s):
if s[0] in "0123456789":
number = s[0]
s = s[1:]
while (s and s[0] in "0123456789."):
number += s[0]
s = s[1:]
result.append(number)
if s:
result.append(s[0])
s = s[1:]
else:
result.append(s[0])
s = s[1:]
return result
然后您需要跟踪一元加减运算。为此，我们引入了一个特殊的 'neg' 操作 - 当您以 postfix 表示法处理此操作时，您只需取反操作数堆栈顶部的值。
您希望在字符串的开头或紧跟在开始的“(”之后进行一元加减运算。在处理数字操作数或结束“)”之后，您将一元标志重置为 False，因为一元加或减号不能出现在这些位置。当一元标志为真时，您必须继续跟踪传入的“+”和“-”，为此使用布尔标志 'neg'。在每个 '-' 处更改 'neg' 状态。当你最终找到一个操作数时——检查 'neg' 标志的状态。如果为 True，则需要将我们特殊的 'neg' 操作放在操作数之后。在结束 ')' 之后放置一个 'neg' 操作有点棘手，需要使用 opStack。
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 3
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
prec["neg"] = 1
opStack = Stack()
postfixList = []
tokenList = tokenize(infixexpr)
print(tokenList)
unary = True
neg = False
for token in tokenList:
if unary and token in "+-":
if token == '-':
neg = not neg
elif isNumber(token):
postfixList.append(token)
if neg:
postfixList.append("neg")
neg = False
unary = False
elif token == '(':
if neg:
opStack.push("neg")
neg = False
opStack.push(token)
unary = True
elif token == ')':
topToken = opStack.pop()
unary = False
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
if not opStack.isEmpty() and opStack.peek() == "neg":
postfixList.append(opStack.pop())
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
输入：
"-(( 1 + 3 ) ) * 4 - ( -9.2 - 0 ) * ( 5 + 8 ) - 4 * (-2)"
输出：
1 3 + neg 4 * 9.2 neg 0 - 5 8 + * - 4 2 neg * -
更新 2020-03-12
如果您想将负数作为单个负操作数处理，而不是像正操作数后跟 'neg' 操作一样，那么您只需要对 infixToPostfix 方法进行非常小的修改。你只需要修改 elif isNumber(token) 分支。不过，我会把它完整地放在这里：
def infixToPostfix(infixexpr):
prec = {}
prec["^"] = 3
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
prec["neg"] = 1
opStack = Stack()
postfixList = []
tokenList = tokenize(infixexpr)
unary = True
neg = False
for token in tokenList:
if unary and token in "+-":
if token == '-':
neg = not neg
elif isNumber(token):
if neg:
postfixList.append("-" + token)
else:
postfixList.append(token)
neg = False
unary = False
elif token == '(':
if neg:
opStack.push("neg")
neg = False
opStack.push(token)
unary = True
elif token == ')':
topToken = opStack.pop()
unary = False
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
if not opStack.isEmpty() and opStack.peek() == "neg":
postfixList.append(opStack.pop())
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
现在输出是
1 3 + neg 4 * -9.2 0 - 5 8 + * - 4 -2 * -
更新 2020-03-13
原文中post我放了下面这句话：
You expect unary plus and minus operations at the start of the string or right after the opening '('.
那里和之前更新中的代码也反映了这一点。我知道这在技术上并不完全正确。操作后也可以预期一元操作。但是，我不想允许像 2+--+-+3 这样的表达式，所以我排除了在操作后进行一元操作的可能性。不幸的是，它也排除了 2^-3 的可能性。如果你希望能够解析像 2^-3 这样的表达式，那么你只需要在另一个操作之后允许一元操作，它需要在 else 分支中添加一行 unary = True ：
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
unary = True # This is the only new line
现在您可以将 2^-3 解析为 2^(-3)。但是，它也允许将 2+-3 解析为 2+(-3)。我总是发现最后一种可能性在计算机语言中非常丑陋，但如果它适合你 - 很好。当然，你也可以只允许在^之后解析一元运算，其他运算之后不解析。
这将需要检查当前标记，并且仅当标记在允许其后一元减号的操作列表中时才将 unary 设置为 True 。
您可以使用 try-except 简单地测试整数或浮点数，这也可以处理负数。问题是在 spaces 上拆分比实际解析令牌要灵活和可靠得多，而且它给使用该函数的人带来了巨大的负担。
您需要分词器功能。幸运的是，python 有一个 tokenizer 模块，尽管第一次使用它并不是那么容易。或者您可以自己编写。
这是使用库的快速实现
from io import StringIO
from tokenize import generate_tokens, NUMBER, OP
def tokenizer(s):
generator = generate_tokens(StringIO(s).readline)
for toknum, tokval, _, _, _ in generator:
if toknum in (NUMBER, OP):
yield tokval
只需更改您的代码即可使用
for token in tokenizer(infixexpr):
修复了更长的数字和十进制数字，并在删除所有 space 的情况下处理您的测试用例：
print (infixToPostfix("((1+3))*4-(9.2-0)*(5+8)"))
1 3 + 4 * 9.2 0 - 5 8 + * -
（我认为这应该是一个独立函数，而不是 class 成员。您可能希望通过取消缩进函数来实现它。）
负数需要多一点，因为分词器会立即 return "-" 作为运算符。您可以编写自己的 tokenizer 函数，将 -55 读取为一个标记，或者您可以跟踪状态并意识到如果您不需要运算符，则减号必须表示下一个标记是负数.参见 How to differentiate '-' operator from a negative number for a tokenizer
除了您询问的问题之外，还有一个问题是一元运算符。如果在表达式前允许使用减号，则必须将其作为运算符处理。亚历克斯在另一个答案中处理了它们，您可以查看 Infix to postfix algorithm that takes care of unary operators 一些实现在后缀中将负数打印为“(-5)”。有些人使用 spaces，尽管如果你没有 spaces 它可以节省 space —— 反正它不是真正的人类可读的。