由于作者在 \(CSP-J\) 的比赛中,曾一度被各类模拟题给搞到心态崩溃,所以决定写此文章。
前置知识:关于表达式中缀与前缀转后缀(不明白前中后缀表达式的自行百度)
对于表达式求值问题,前缀与后缀往往比中缀容易处理,并且也没有括号,一般把中缀改成后缀。
前缀也能有后缀的效果,但是为了统一与方便,也为了在考场上不出错,可以也通过某些方式转变。
1.关于表达式求值
首先表达式是一类形如 A operation B
的字符串,并且所有运算符号都需要优先级,有时会有括号,不同的括号也需要优先级,同时可能会有从左往右算,或者从右往左算。
- 对于某些求值,倘若需要从右往左算,可以直接把表达式反转。
- 考虑没有括号,但是有不同运算符号且优先级不同的表达式:
我们可以