<p><strong>免责声明:</strong>解决方案可能会使用各种不相关的概念,无法在此处进行解释</p>
<p>要获得优先级,必须正确解析输入。有几种方法可以做到这一点;一个常见的是Dijkstra的<a href="https://en.wikipedia.org/wiki/Shunting-yard_algorithm?oldformat=true" rel="nofollow noreferrer">shunting yard</a>算法。<br/>
由于这只是一个示例,我们将放弃良好实践(错误处理、类)以获得更简洁的代码</p>
<p>首先,我们需要列出先例。更高的优先级意味着操作符具有更高的优先级,因此它执行得更早</p>
<pre class="lang-py prettyprint-override"><code>precedences = {
'^': 3,
'*': 2, '/': 2,
'+': 1, '-': 1
}
</code></pre>
<p>然后,我们需要将操作与每个操作符关联起来。为此,我们可以使用<code>operator</code>模块中的函数:</p>
<pre class="lang-py prettyprint-override"><code>from operator import pow, truediv, mul, add, sub
do = {
'^': pow,
'*': mul, '/': truediv,
'+': add, '-': sub
}
</code></pre>
<p>最后,我们需要实现决定何时计算表达式的逻辑。首先,我们比操作多了一个数字,所以我们将其放在堆栈上:</p>
<pre class="lang-py prettyprint-override"><code>def shunt(numbers, operations):
stack = [numbers.pop(0)]
operators = []
</code></pre>
<p>然后,我们处理每个运算符对</p>
<pre class="lang-py prettyprint-override"><code> while len(numbers):
operator = operations.pop(0)
precedence = precedences[operator]
</code></pre>
<p>当一个操作的优先级(执行时间早于当前操作)高于当前操作时(使用<code>do</code>字典)对其求值。我们从堆栈中删除左操作数和右操作数,并从<code>do</code>中查找适当的函数以计算结果:</p>
<pre class="lang-py prettyprint-override"><code> while operators and precedences[operators[-1]] >= precedence:
[left, right], stack[-2:] = stack[-2:], []
stack.append(do[operators.pop()](left, right))
</code></pre>
<p>然后,我们将当前运算符和编号附加到堆栈:</p>
<pre class="lang-py prettyprint-override"><code> operators.append(operator)
stack.append(numbers.pop(0))
</code></pre>
<p>所有数字和运算符用完后,我们评估其余的运算符,直到只剩下一个数字,然后返回:</p>
<pre class="lang-py prettyprint-override"><code> while len(stack) > 1:
[left, right], stack[-2:] = stack[-2:], []
stack.append(do[operators.pop()](left, right))
return stack[0]
</code></pre>
<p>把它们放在一起(<a href="https://tio.run/##lVPbbtswDH22voLzHmInStbEGIYFSH/EcAEnUmphtiRI8roL9u0ZKdu1U/SlT5J4OTw8pOzv0Bhd3G5XZzowVro6GAeqs8YFsOaFQ3C9FOonh65vOdRCcPD9mTHr5EUKqS/Swwn@smT1tDpCwfGyxsuBw@pLPNGwwcseDVs62T/GhFnkUJkxK9aIeVPZMTvWjflUnBDkFXzT65DpvjtL5/lIXxnt8yNLfKgvP7BKOfp31tjsIa9YMrVJvEt8vzSqldBKPUFR@msUBs3AIwi65/YxYKFFOeUhcPIZBuzQSCdBeaj1LHJo6gBnpYWHoJ6bIB2K3TsNKoDSwVCw/IXQ3mNpRBuwZva1Fu9W9uV2X1XwuORFHSVlK6@Bg6NqFY6RFCq3h2OFLcwPHkVJBgF3tbVSi0yYGT6KkFfZAi3PF4r5KWkykPMO7X4k@XIEMS6HR9gT5Q8x/ihhJ6PcA85DdWuVpmEqbfuQ5WzkRMZPJ0hT5DPypr1Zd7XNcEw8Ruy8bVXIUkjztxs2wi0iWHLF8SMWrSz64Y@yb7fYjFtonRpWnBwcsLPTAPHqoCwa@NKJO9O3gTR674cQ9gSQnlJUJIaj7V6BWwEH/K5r2LBvUEDBNrBmB/gK39kT3th/" rel="nofollow noreferrer">Try it online!</a>):</p>
<pre class="lang-py prettyprint-override"><code>from operator import pow, truediv, mul, add, sub
precedences = {
'^': 3,
'*': 2, '/': 2,
'+': 1, '-': 1
}
do = {
'^': pow,
'*': mul, '/': truediv,
'+': add, '-': sub
}
def shunt(numbers, operations):
stack = [numbers.pop(0)]
operators = []
while len(numbers):
operator = operations.pop(0)
precedence = precedences[operator]
while operators and precedences[operators[-1]] >= precedence:
[left, right], stack[-2:] = stack[-2:], []
stack.append(do[operators.pop()](left, right))
operators.append(operator)
stack.append(numbers.pop(0))
while len(stack) > 1:
[left, right], stack[-2:] = stack[-2:], []
stack.append(do[operators.pop()](left, right))
return stack[0]
</code></pre>