我是编程新手,为了变得更好,我开始了一个小项目。我想做一个不那么基本的外壳计算器,基本的方法很快就完成了,我学到了很多。但我的新目标是评估完整的代数表达式,如:(2+3)^(80/(3*4))
我认为一种算法会派上用场,可以像人类一样"一步一步"地完成这件事——解决整个事情的一点,然后重新开始。所以我想先检查一下所有插入的代数符号:(术语是用户输入)
open_brackets =[i.start() for i in re.finditer('(',str(term))]
close_brackets =[i.start() for i in re.finditer(')',str(term))]
powers =[i.start() for i in re.finditer('^',str(term))]
mult =[i.start() for i in re.finditer('*',str(term))]
div =[i.start() for i in re.finditer('/',str(term))]
plus =[i.start() for i in re.finditer('+',str(term))]
minus =[i.start() for i in re.finditer('-',str(term))]
现在我有了这些信息,我认为寻找最右边的开括号并找到相应的闭括号可能会很有用:
last_open_bracket = open_brackets[len(open_brackets)-1]
next_closed_bracket = 0
for i in close_brackets :
if last_open_bracket < i :
next_closed_bracket = i
break
从那时起,我只会遇到问题,因为我不知道如何构建整个事情,而且我已经搞砸了好几次了。查看这些括号内部,并检查它们之间的代数符号显然是有用的。权力的一个例子是:
for i in powers :
if (last_open_bracket < i) and (next_closed_bracket > i) :
现在,一旦我找到了"^"的位置,我就可以在"^"左边逐步前进,直到我碰到了不是int或"类型的东西。由于这在浮点运算中使用,更具体地说,我搜索下一个代数符号或括号。以此类推,直到我有2个数字,然后我可以取它的幂。然后将原始输入中用于此计算的所有符号和数字切片,并在正确的位置添加计算结果,然后重新开始。
我的问题是处理括号内可能发生的所有不同场景,例如
- 多项操作,即(2+3+4)
- 识别(-9)或-(9)中的"-"不是减法的调用
还有在某些情况下如何处理不同的括号,例如,我早些时候建议将使用的所有符号和数字都去掉,但在不同的情况下,我们需要不同的方法:
- (9)-->9
- (2+3)-->5
- (-2)^2-/->-2^2
正如你所看到的,我需要一些思考帮助,我不知道如何概念化这个算法。我希望你能帮助我,并有一个美好的一天!
我见过一些解析器,也写过一些自己的解析器,但我从未见过像您正在尝试的算法。你的困难可能意味着你应该使用另一种整体算法。
我建议你一次从左到右扫描表达式字符串中的一个字符,并对每个字符进行适当的操作。如果您想要简单,可以使用PEMDAS和一组例程来制作递归算法。您的顶级计算一个表达式,下一个是圆括号组,下一次是求幂,下一步是乘法和除法,最后一次是加法和减法。您还需要一个例程来评估数字文字,一个用于否定,一个用作一元加号。
还有其他方法,例如为每个运算符使用一个令牌,将事物放在堆栈上,以及使用一个为每个运算符提供操作顺序的字典。这里的求幂要小心,因为它的顺序是从右到左,而不是从左到右。但您的需求似乎相当简单,递归方法对您来说会更简单。
尽管代数语言非常有限,但这并不是一项微不足道的工作。
您当然可以按照其他答案的建议编写自己的解析器。或者,您可以使用解析器生成器根据语法规则生成解析器。
以下是一个可能的解决方案草图:
你首先需要为你的代数语言定义一个语法。维基百科上有一个类似语言的正式语法。
您尝试评估的语言似乎与上下文无关。
有不同种类的规则来指定形式语法。其中一种被称为EBNF(Extended Backus Naur Form)。
上下文无关语言的语法通常被定义为包含终端符号和非终端符号的生成规则,规则的左手边正好包含一个非终端符号。
在您的案例中,终端符号是数字(0到9)、括号和运算符+-/*^
。
对于你的语言,我想一个新的非终端符号S
就足够了。
您的规则可能如下所示:
S -> ( <S> + <S> );
S -> ( <S> - <S> );
S -> ( <S> / <S> );
...
S -> 0|1|2|3|4|5|6|7|8|9;
这是一个很好的工具来尝试你的上下文无关规则:
一旦指定了语法,就可以使用语法分析器生成器(例如ANTLR)生成一个语法分析器,如果输入字符串符合查询,则该语法分析器将把输入字符串转换为解析树,否则将抛出异常。
维基百科为不同种类的语言提供了一个解析器生成器列表。您应该在本节中查看上下文无关语言。
然后,您将需要使用结构递归来评估抽象语法树。
您可能需要考虑的一件事是自下而上的解析器。您可以通过根据操作顺序进行筛选,在递归解析方法中使用正则表达式来使用它。首先,你把括号里的内容传下来进行解析。然后,你使用你的能力并将其传递到解析中。然后,从左到右进行乘法和除法运算,并将它们传递到解析中。最后,从左到右,进行加法和减法运算,并将它们传递到解析中。在底层(即*、/、-、+、^),在将表达式传递回之前先对其进行评估。关于这个主题的维基百科文章可以在这里找到。
您应该熟悉后缀和前缀表示法,在这些表示法(双向)和中缀表示法之间转换的基本算法,最后是分流场算法。
这些将回答您的算法问题。SYA甚至适用于函数标记和嵌套函数。
您需要花费一些时间来学习各种运算符的优先级和左/右关联性。