IT公司面试题收集整理---数据结构相关复习---算术表达式求值算法（带括号递归运算）.pdf

BBS.SASAOO.COM -- 财经 医疗 软件 娱乐 养生 综合信息论坛 IT 公司面试题收集整理数据结构相关复习算术表达式求值算法（带括号递 归运算） 首先声明，这仅仅是一个算法的雏形，实用率几乎为0。我只说这个思想。代码是用java 写的，可以运行，但是表 达式和中间值不能为负数【因为我用的java 的字符串截取，如果使用C 语言的话，在不带括号的情况中，就没有 这个问题了，也可以为负数】，下面我写出我的想法，然后你就知道为什么不能为负数了。 第一：判断有没有括号，有的话，遇到一个右括号，那么就截取对应的左括号与右括号之间的字符串，还要让字符 串加一个=。【因为没有括号的方法中限制的】 第二：如果现在只有加减乘除的话，比如说1+2*3+4+5-5=，就进入循环 第三：分为两个栈，遇到一个符号的时候，先放数字栈数据，然后比较符号栈的顶部，与即将放入栈的符号，进行 比较。如果即将进栈的优先级比顶部的优先级低，那么 数字栈出两个，符号栈出一个，进行计算，结果放到数字栈，即将放入栈的符号现在也放入栈。 第四：遇到等号的话，全部出栈。栈为空的话，返回数字栈的第一个值。【即最终结果】 [java] view plaincopyprint? 1. package 计算器; 2. 3. public class Demo { 4. public double number[] = new double [6];// 数字栈 5. public char sign[] = new char[6];// 符号栈,*/=优先级大于+-优先级 6. public int topNum = -1;// 头指针 7. public int topSign = -1;// 头指针 8. 9. // 表达式求值，带括号算法,注意：表达式一定要正确，并且不能出现负数，因为这个算法用的是字 符串截取 10. public double evaluation(String string) throws Exception {// 参数代表正确的表达式 11. double result = 0; 12. // 如果式子中包含括号，截取括号匹配中的字符串 13. if (string.contains(() || string.contains())) { 14. int temp = 0; 15. fo r (int i = 0; i string.length(); i++) { 16. if (string.charAt(i) == () {// 碰到左括号，记录下来 17. temp = i; 18. continue; 19. } 20. if (string.charAt(i) == )) {// 碰到右括号，进行递归，实际上相当于出栈 21. string = string.substring(0, temp) 22. + evaluation(string.substring(temp + 1, i) + =)// 加个等号继续递 归 BBS.SASAOO.COM BBS.SASAOO.COM -- 财经 医疗 软件 娱乐 养生 综合信息论坛 23. + string.substring(i + 1); 24. System.out.println(string); 25. i = -1; 26. continue; 27. } 28. } 29. } 30. // 现在式子