根据逆波兰式来算出表达式的值。首先说明一下逆波兰式，逆波兰式是巴普通表达式的中缀表达方法，例如，3 + 5 * 4， （3 + 5）* 4 替换成后缀表达式，逆波兰式不需要括号，且不会产生歧义。
例如，之前的两个表达式用逆波兰式表达就是，3 5 4 * +， 3 5 + 4 *。普通式子转换成逆波兰式就要注意两点：第一，由于涉及的运算符都是双目的（不包括括号），运算符要放在第二个操作数后面；第二， 如果第二个操作数，由于运算符号的优先性，是一个表达式，就先写出表示第二个操作数的逆波兰式，之后加上操作符。这一题不需要涉及到普通的表达式转换成逆波兰式，所以我们只考虑如何算出，逆波兰式的值，计算逆波兰式的值十分简单，每次碰到一个操作符，就把对应的操作数的值算出来，也就是两个操作数经过计算变成一个操作数，直到计算完所有的操作符。值得注意的一点事，操作符永远比操作数少1。基本的思路就是维护一个操作数的栈，每次遇到一个操作符，弹出栈顶的两个元素，计算完入栈，直到计算完所有，栈里最后一个就是表达式的值。代码如下：
Follow up：如何把表达式转换成逆波兰表达式
No comments:
Post a Comment