步骤一:中缀表达式转后缀表达式
①设立一个操作符栈,用以临时存放操作符;设立一个数组或队列,用以存放后缀表达式。
②从左到右扫描中缀表达式,如果遇到操作数就直接把它们加入到后缀表达式中。
③如果碰到操作符op,就将其优先级与操作符栈的栈顶操作符的优先级比较
· 若op的优先级高于栈顶操作符的优先级,则压入操作符栈。
· 若op的优先级低于或等于栈顶操作符的优先级,则将操作符栈的操作符不断弹出到后缀表达式中,直到op的优先级高于栈顶操作符的优先级
④重复上述操作,直到中缀表达式扫描完毕,之后若操作符栈中仍有元素,则将它们依次弹出至后缀表达式中。
操作符的优先级:乘法==除法>加法==减法,在具体实现上可以用map建立操作符和优先级的映射。
步骤二:计算后缀表达式
从左到右扫描后缀表达式,如果是操作数,就压入栈;如果是操作符,就连续弹出两个操作数(注意:后弹出的是第一操作数,先弹出的是第二操作数),然后进行操作符的操作,生成的新操作数压入栈中。当栈中就存在一个数时,就是最终的答案。
· 注意除法可能导致浮点数,因此操作数类型要设成浮点型。
代码见胡凡算法笔记 P249