检查布尔数学公式的形式是否正确

Question

我正在创建一个程序，它将布尔表达式作为字符串输入，并将中缀公式转换为后缀公式，同时确保公式的形式有效。我很难找到一种方法来检查输入的公式是否有效。不允许导入（使用内置的python函数/方法），允许循环和递归。如果公式无效，请返回None。

公式可以包含：

variables in 'abcdefghijklmnopqrstuvwxyz'
operators in '-+*'

"x" 
"-y" 
"(x*y)" 
"((-x+y)*(-y+x))" 

"X" variable not lower case letter 
"x*y" missing parentheses 
"-(x)" extraneous parentheses 
"(x+(y)*z)" mismatched parentheses

一些转换示例如下：

(x+y) -> xy+
(x*y) -> xy*
-(x+y) -> xy+-
-x -> x-
((x*y)+(z*x)) -> xy*zx*+

不需要一个完整的工作程序，一个检验公式是否有效的算法就可以了。

我的当前实现将公式从中缀转换为后缀：

def infix_to_postfix(infix_expression):
    precedence  = {}
    precedence["*"] = 2
    precedence["+"] = 2
    precedence["-"] = 2
    precedence["("] = 1
    storage_stack = Stack()
    postfix_list = []
    tokenList = list(infix_expression)
    for token in tokenList:
        if(token not in "-+*()"):
            postfix_list.append(token)
        elif(token == '-'):
            storage_stack.push(token)
        elif(token == '('):
            storage_stack.push(token)
        elif(token == ')'):
            topToken = storage_stack.pop()
            while(topToken != '('):
                postfix_list.append(topToken)
                topToken = storage_stack.pop()
        else:
            while(not storage_stack.is_empty() and precedence[storage_stack.peek()] >= precedence[token]):
                postfix_list.append(storage_stack.pop())
            storage_stack.push(token)
    while(not storage_stack.is_empty()):
        postfix_list.append(storage_stack.pop())
    result = "".join(postfix_list)
    return result

((a+b)*(c+d))
F1 = (a+b)
F2 = (c+d)
((a+b)*(c+d)) = (F1 * F2)
If F1 and F2 are valid, then the whole thing is valid.

Answer 1

这是一个老问题，但这里有一个潜在的解决方案，有人有相同的问题。

import re


def formula(string):
    if not string: return 0
    string = re.sub("[^0-9+*/%-=]", "", string)

try:
    string, result = string.split("=")
    return eval(string) == int(result)
except:
    return 0