问题 7069 --求逆波兰表达式

7069: 求逆波兰表达式★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 3
[提交][状态][命题人:]

题目描述

    标准的表达式如“A+B”,在数学上学名叫中缀表达式,原因是运算符号在两个运算对象的中间。相对应的还有前缀表达式,如“+-A*BCD”,转换成中缀表表达式为:"A-B*C+D",后缀表达式,比如前面所述的中缀表达式转换为后缀表达式为:“ABC*-D+”
    为了纪念波兰数学家鲁卡谢维奇(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)从左往右扫描表达式
  ①遇到数字,入栈
  ②遇到运算符,把处于栈最上方的两个元素依次出栈,用运算符计算,并将计算结果压入栈中;
  ③重复①②步骤,直至表达式扫描结束。

输入

输出

样例输入
Copy
6 8 2 - 2 * 3 / +
样例输出
Copy
10.0

提示

来源

[提交][状态]