一年多未更新博客了,此贴纯刷屏用。前段做培训留的题目,自己作了下,感觉蛮简单的代码测的时候还是有不少坑,只做了整数版本,懒得再弄了。
import java.util.ArrayList; import java.util.Stack; /** * 逆波兰表达式实现四则运算 * * @author Duanhengbin * */ public class Exercise02 { // 四则运算式中的符号 static String OPERATORS = "+-*/()"; /** * 根据输入的中缀表达式列表计算 * * @param aPstfix * @return */ public static int RpnComputer(String expression) { Stack<String> stack = new Stack<String>(); int num1, num2, result; num1 = num2 = result = 0; ArrayList<String> aPstfix = createPstfix(expression); for (String cell : aPstfix) { // 数字的场合 if (OPERATORS.indexOf(cell) == -1) { stack.push(cell); // 符号的场合 } else { // TODO: 支持带小数的数字计算 num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); switch (cell) { case "+": result = num2 + num1; break; case "-": result = num2 - num1; break; case "*": result = num2 * num1; break; case "/": result = num2 / num1; break; default: // TODO: throw Exception } stack.push(Integer.toString(result)); } } return result; } /** * 根据输入表达式字符串生成后缀表达式列表 * * @param s * @return */ private static ArrayList<String> createPstfix(String s) { String[] cells = extractArrayFromExp(s); ArrayList<String> results = new ArrayList<String>(); Stack<String> stack = new Stack<String>(); for (String cell : cells) { if (OPERATORS.indexOf(cell) == -1) { // 数字的场合 results.add(cell); } else { // 符号的场合 if (cell.equals(")")) { // 待入栈“)”时,只出不入 results.addAll(popStack(stack, cell)); } else if (stack.isEmpty() || stack.peek().equals("(") || cell.equals("(") || "*/".contains(cell) && "+-".contains(stack.peek())) { // 这些为只入不出的情况 stack.push(cell); } else { // 其他情况 先出后入 if ("*/".contains(cell)) { results.add(stack.pop()); } else { results.addAll(popStack(stack, cell)); } stack.push(cell); } } } if (!stack.isEmpty()) { results.addAll(popStack(stack, "")); } return results; } /** * 返回从当前栈中出栈且需要加入到表达式的符号列表 * * @param stack * @return */ private static ArrayList<String> popStack(Stack<String> stack, String inSign) { ArrayList<String> rtn = new ArrayList<String>(); // 将遇到“(”为止所有符号出栈 while (!stack.isEmpty() && !"(".equals(stack.peek())) { rtn.add(stack.pop()); } // 入栈“)”时,将“(”出栈 if (inSign.equals(")")) { stack.pop(); } return rtn; } /** * 先将符号两侧增加空格,再替换多个空格为一个空格,最后用空格切分,将表达式拆分成数字与符号列表 * * @param s * @return */ private static String[] extractArrayFromExp(String s) { String sOperator = null; // 在符号前后添加空格 for (int i = 0; i < OPERATORS.length(); i++) { sOperator = OPERATORS.substring(i, i + 1); s = s.replaceAll("\\" + sOperator, " " + sOperator + " "); } // 将多个空白字符:[\t\n\x0B\f\r] 替换为一个空格 注意这里正则简记法\s s = s.replaceAll("[\\s]+", " "); return s.trim().split(" "); } }
测试代码
import static org.junit.Assert.assertEquals; import java.util.Arrays; import java.util.Collection; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import org.junit.runners.Parameterized.Parameters; import exercise.Exercise02; @RunWith(Parameterized.class) public class Exercise02Test { private String exep; private String result; @Parameters public static Collection<String[]> data() { return Arrays.asList(new String[][] { { "9 + (3 -1)* 3+10/2 ", "20" }, { "((((2-3)*(8/2-1))))", "-3" }, { "((1+2+3) * 2)-10+4/2*3 ", "8" }, { "(1+2+3+4*5*6/2-9)", "57" }, { " (1*2*3*8-5*6/2/3/5-9)", "38" }, { " (1*2*3*6/9/2*10-(1+2)*4) ", "8" }, { "10-9/3+3*(2/(1/1))", "13" } }); } public Exercise02Test(String exep, String result) { this.exep = exep; this.result = result; } @Test public void testRpnComputer() { assertEquals(result, String.valueOf(Exercise02.RpnComputer(exep))); } }
相关推荐
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
逆波兰表达式的C++实现,用类封装,用于计算逆波兰表达式
使用c语言实现,将给定的运算表达式翻译成逆波兰表达式的形式
逆波兰表达式用堆栈实现,读入表达式的值,利用堆栈计算该表达式的值,同时校验后缀表达式是否正确。
学习YACC(BISON)的语法结构,编写YACC(BISON)程序,生成能够分析和计算逆波兰表达式,构建逆波兰计算器。根据提示,在右侧编辑器补充代码,实现加法(+)、减法(-)、乘法(*)、除法(/)、乘方(^)以及取负运算(n)。
使用C++模拟了计算器的四则运算,包括加减乘除以及括号优先级运算,主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式,然后再进一步计算逆波兰表达式的值,具体算法思路在主页,资源包括一个main.cpp文件...
实现逆波兰表达式其实并不是很难,但是为什么要将看似简单的中缀表达式转成后缀表达式呢? 其实中缀表达式只是对人类而言是简单的,然而对于计算机来说,中缀表达式是一个非常复杂的结构。而后缀表达式对于计算机是...
主要介绍了Python实现处理逆波兰表达式操作,结合实例形式分析了逆波兰表达式的概念、原理及Python针对逆波兰表达式的定义与计算相关操作技巧,需要的朋友可以参考下
1. 逆波兰表达式的介绍 2. 中缀转后缀的原因 3. 存储特点和原理 4. 栈实现中缀转后缀的思路 5. 代码实现 6. 注意事项 一,逆波兰表达式的介绍 前缀: 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前 举例...
在程序设计中,可能碰到需要对字符串数学表达式求值...后缀表达式也称逆波兰表达式 因其使表达式求值变得轻松,所以被普遍使用。 程序解析字符串表达式,将其转换为逆波兰式,然后生成表达式二叉树,最后计算表达式值。
实现了中缀式变后缀,语法树的生成,可以进行简单的计算
主要介绍了python实现逆波兰计算表达式的方法,较为详细的分析了逆波兰表达式的概念及实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
项目中设计到了用户配置表达式,动态运行结果,采用逆波兰算法实现表达式的计算
输入一个含有运算符和运算函数的表达式,计算其结果。表达式中包括: ①数值:整数、实数②一般运算符:正号,负号,加、减、乘、除、求模、乘方、括号等
/* 表达式计算 */ /* 调用方式:CalcExp('1+max(0.5,sin(1))+sum(1,2^3,mod(5,3))', res, infoStr) */ /* 带符号参数调用方法,先调用符号定义AddSignParam,再调用 CalcExp: */ /* AddSignParam(['a','s'], ...
利用两个栈实现中缀表达式求值功能 输入一个中缀表达式 即可计算出结果
用堆栈实现中缀表达式转后缀,并计算后缀表达式的结果。
计算器实现了基本的运算功能,可做表达式计算,以逆波兰式运算
本文实例为大家分享了C语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下 逆波兰表达式: 逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。 例:5 – 8*(6 + 7) +...