逆波兰表示法
逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 * 5”与“(3 - 4)*5”不相同,但后缀记法中前者写做“3 4
5 * -”,无歧义地表示“3 (4 5 *) −”;后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,和能很快求值。
注意:逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符,它的操作数写法仍然是常规顺序,如,波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”;数字的数位写法也是常规顺序。
代码实现:
package test;
import java.util.Stack;
public class evalRPN {
public static void main(String[] args) {
// String[] tokens = {"2", "1", "+", "3", "*"};
String[] tokens = { "4", "13", "5", "/", "+" };
// evalRPN.evalRPN(tokens);
System.out.println(evalRPN.evalRPN(tokens));
}
public static int evalRPN(String[] tokens) {
Stack<String> stack = new Stack<String>();
for (String s : tokens) {
switch (s) {
case "+": {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
String c = String.valueOf(a + b);
stack.push(c);
break;
}
case "-": {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
String c = String.valueOf(b - a);
stack.push(c);
break;
}
case "*": {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
String c = String.valueOf(a * b);
stack.push(c);
break;
}
case "/": {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
String c = String.valueOf(b / a);
stack.push(c);
break;
}
default:
stack.push(s);
}
}
return Integer.valueOf(stack.pop());
}
}
分享到:
相关推荐
计算器中使用逆波兰表示法计算器中使用逆波兰表示法计算器中使用逆波兰表示法计算器中使用逆波兰表示法
编译原理-逆波兰表示法C++
逆波兰表示法和表达式四元式.pdf
本人自己写的程序,绝对通过测试的(这就是我课程设计的题目).输入表达式时每个字符间用空格格开,最后用#结束输入 显示结果时先显示所转化成的逆波兰式,然后是结果
读取输入字符存入数组中,逐个扫描数组元素遇操作数进栈,遇运算符计算并将结果进栈继续上述过程,直至数组读取完
用逆波兰(后缀表示)实现四则运算,从文件随机读取题目,对该次成绩进行存储并与上次成绩进行比较给出评语,提供用户接口,用户可自己添加题目到题库中。
表达式求值的经典算法(逆波兰) 数据表达式类 1. 可完成中缀表达式式到后缀表达式的转换 2. 后缀表达式求值.
博客配套资源https://blog.csdn.net/qq_32439305/article/details/105620451
rpn - 反向波兰符号 PHP 类这个 PHP 类实现了一个逆波兰表示法 (RPN) 评估,它支持数字、字符串和用户定义的函数以及用于数字/字符串操作的内置 PHP 函数。 #####Live 示例和其他项目可以在我的 [development] ( ) ...
RPNCalc 是一个基于命令行的逆波兰表示法 (RPN) 计算器。 RPN 计算器使复杂计算变得非常简单,尤其是在涉及括号的情况下。 举个简单的例子,考虑用以下方法求解 X:x = SQRT((((5+3) * 8)/2) ^ 6) 使用 RPN 计算器,...
逻辑可满足性更多关于可满足写入ONP(逆波兰表示法)逻辑式的满足性有关此示例中使用的Metoda表格semantycznych(语义表方法)的更多信息,请技术领域语言:Python 3.6 库:复制发射将所有文件放在一个文件夹中运行...
在程序设计中,可能碰到需要对字符串数学表达式求值...后缀表达式也称逆波兰表达式 因其使表达式求值变得轻松,所以被普遍使用。 程序解析字符串表达式,将其转换为逆波兰式,然后生成表达式二叉树,最后计算表达式值。
这是因为栈数据结构可以帮助我们实现后缀表达式(逆波兰表示法)的解析和计算。 以下是一个简单的Python代码示例,用于解析和计算后缀表达式(也称为逆波兰表示法): def calculate(stack): while True: token = ...
根据逆波兰表示法,求表达式的值。 有效的运算符包括 + ,- ,* ,/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ 思路 ...
android 课堂上的第一个作业,基于Android 4.2.2 做的一个简易计算器,采用逆波兰算法,将中缀表达式转换为后缀表达式,可解析带括号的四则运算。
简介:根据逆波兰表示法,求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。编辑时间:2020.2.13
逆波兰计算器程序代码这种表示法用在某些袖珍计算器及某些语言中),允许使用26个具有单个大写英文字母变量名的变量,允许对最近计算的结果进行引用(使用某特定的名字,比如小写字母v或?)。
《编译原理》期末试题(一) 一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分) 1.编译程序是对高级语言程序的解释执行。...6.逆波兰表示法表示表达式时无须使用括号。 (√ )
以逆波兰表示法计算算术表达式的值。 有效的运算符是 +、-、*、/。 每个操作数可以是整数或其他表达式。 笔记: 两个整数之间的除法应向零截断。 给定的 RPN 表达式始终有效。 这意味着表达式将始终评估为结果,并且...