为了纪念波兰数学家鲁卡谢维奇(Jan Lukasiewicz),后缀表达式被称为逆波兰表达式。逆波兰表达式是一种把运算符后置的算术达式,例如普通的表达式2+3的逆波兰表示法为23+。逆波兰表达式的优点是运算符之间不必用括号改变运算次序,运算符放在两个运算对象之后,所有计算按格地由左往右进行。
例如:5*(27-13)+90对应的逆波兰表达式为5 27 13 - * 90 +,其中用空格作为操作数(运算符)的间隔符。计算过程如下:
5 27 13 - * 90 + =5 14 * 90 + =70 90 + =160
本题要求计算逆波兰表达式的值,为简单起见,假设操作数为正整数,运算符只包括“+-*/”四个。
设计算法:
(1)用一个栈存储数字
(2)从左往右扫描表达式
①遇到数字,入栈
②遇到运算符,把处于栈最上方的两个元素依次出栈,用运算符计算,并将计算结果压入栈中;
③重复①②步骤,直至表达式扫描结束。