import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
/*
*测试 -5*(10/(2*4.5-4)+(-3/1.5+4)*(-2))/(-2/1-(-1))+12=2.0
*/
public class Calc {
// 求四则运算表达式运算结果
public static double excute(String value) throws Exception {
List<String> list = toList(value);// 按顺序转成数字符号list 即中序表达式
list = toSuffixExpressionList(list);// 转成逆波兰式数字符号list 即后序表达式
double result = suffix_excute(list);// 求逆波兰式结果
System.out.println(value + "=" + result);
return result;
}
// 表达式划分成中序list 即从左到右数字符号分开
private static List<String> toList(String value) {
// 开始为-时加上0
if ("-".equals(value.substring(0, 1))) {
value = "0" + value;
}
int begin = 0;
int end = 0;
String item;
List<String> resultList = new ArrayList<String>();
for (int i = 0, len = value.length(); i < len; i++) {
item = value.substring(i, i + 1);
if (isOperator(item)) {
// 负数跳过
if ("-".equals(item) && "(".equals(value.substring(i - 1, i))) {
continue;
}
end = i;
// 前一个非符号时加上数字
if (begin != end) {
resultList.add(value.substring(begin, end));
}
// 加上符号
resultList.add(value.substring(end, end + 1));
begin = end + 1;
}
}
// 加上最后一个数字
if (begin != value.length()) {
resultList.add(value.substring(begin));
}
// System.out.println(value + "=" + list);
return resultList;
}
// 中序list转换成逆波兰式list 左右根
private static List<String> toSuffixExpressionList(List<String> list) throws Exception {
Stack<String> operatorStack = new Stack<String>();// 符号栈
Stack<String> resultStack = new Stack<String>();// 结果栈
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
String item = iter.next();
if (isOperator(item)) {
if (")".equals(item)) {
// 遇到)时符号栈一直弹出并压入结果栈直到遇到(,弹出(废弃,结束。
while (!(operatorStack.isEmpty() || "(".equals(operatorStack.peek()))) {
resultStack.push(operatorStack.pop());
}
// 弹出(
if (!operatorStack.isEmpty() && "(".equals(operatorStack.peek())) {
operatorStack.pop();
} else {
throw new Exception("(少了");
}
} else if ("(".equals(item)) {
// 遇到(时直接入符号栈,结束
operatorStack.push(item);
} else {
// 遇到其他运算符时与符号栈顶(若符号栈顶为空或(时直接入符号栈,结束)运算比较 若比栈顶高直接入符号栈,结束
// 否则符号栈弹出并压入结果栈 并再执行与符号栈顶比较直到弹入符号栈,结束
while (!(operatorStack.isEmpty() || "(".equals(operatorStack.peek()))) {
if (compareOperator(item, operatorStack.peek()) < 1) {
resultStack.push(operatorStack.pop());
} else {
break;
}
}
operatorStack.push(item);
}
} else {
// 数字时直接入结果栈
resultStack.push(item);
}
}
// 符号栈全部弹出并压入结果栈
while (!operatorStack.isEmpty()) {
if ("(".equals(operatorStack.peek())) {
throw new Exception("(多了");
}
resultStack.push(operatorStack.pop());
}
// 结果栈弹出并反序得出最终结果
iter = resultStack.iterator();
List<String> resultList = new ArrayList<String>();
while (iter.hasNext()) {
resultList.add(iter.next());
}
// System.out.println(list + "=" + rtList);
return resultList;
}
// 逆波兰式list 求值
// 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op
// 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
private static double suffix_excute(List<String> list) {
Stack<Double> resultStack = new Stack<Double>();
Iterator<String> iter = list.iterator();
Double num1;
Double num2;
while (iter.hasNext()) {
String item = iter.next();
if (isOperator(item)) {
num2 = resultStack.pop();
num1 = resultStack.pop();
resultStack.push(doOperator(num1, num2, item));
} else {
resultStack.push(Double.parseDouble(item));
}
}
return resultStack.pop();
}
// 比较两运算高低 1 1>2, 0 1=2 -1 1<2
private static int compareOperator(String operator1, String operator2) {
if ("*".equals(operator1) || "/".equals(operator1)) {
return ("-".equals(operator2) || "+".equals(operator2)) ? 1 : 0;
} else if ("-".equals(operator1) || "+".equals(operator1)) {
return ("*".equals(operator2) || "/".equals(operator2)) ? -1 : 0;
}
// 这个到不了
return 1;
}
// +-*/基本运算
private static double doOperator(Double num1, Double num2, String operator) {
if ("+".equals(operator)) {
return num1 + num2;
} else if ("-".equals(operator)) {
return num1 - num2;
} else if ("*".equals(operator)) {
return num1 * num2;
} else if ("/".equals(operator)) {
return num1 / num2;
}
// 这个到不了
return -1;
}
// 是否为运算符
private static Boolean isOperator(String value) {
return "(".equals(value) || ")".equals(value) || "+".equals(value) || "-".equals(value) || "*".equals(value)
|| "/".equals(value);
}
public static void main(String[] args) {
try {
excute("-5*(10/(2*4.5-4)+(-3/1.5+4)*(-2))/(-2/1-(-1))+12");
} catch (Exception e) {
e.printStackTrace();
}
}
}
结果
-5*(10/(2*4.5-4)+(-3/1.5+4)*(-2))/(-2/1-(-1))+12=2.0
分享到:
相关推荐
数据结构---用C写的求逆波兰式数据结构---用C写的求逆波兰式数据结构---用C写的求逆波兰式
通过把输入的中缀表达示转换为逆波兰式实现整数及小数的四则运算,为了简便,这个程序只支持小括号,中括号和大括号暂不支持,需要的话自己插入几句代码就行了。 gcc下编译通过,没在window下测试。
工具提供四则运算解析功能。将.hpp文件引入C++工程中即可使用。详情用法参见文件中注释
逆波兰式 java编写,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
编译原理实验报告,中间代码---逆波兰式的C++源代码,
在MFC中利用逆波兰式求值画出一元函数表达式的曲线图
在程序设计中,可能碰到需要对字符串数学表达式求值的问题,常用的方法是解析表达式,生成二叉树,然后进行计算。...程序解析字符串表达式,将其转换为逆波兰式,然后生成表达式二叉树,最后计算表达式值。
对逆波兰表达式求值,逆波兰式即后缀表达式,计算机容易求值。如23+4— 求值为1。 1、问题描述 读入一个后缀表达式,计算该表达式的值,同时要效验后缀表达式是否正确。 2、操作数的顺序与等价的中缀表达式中操作数...
表达式求值(带括号,+,-,*,/的) 用栈实现,C语言代码
本人自己写的程序,绝对通过测试的(这就是我课程设计的题目).输入表达式时每个字符间用空格格开,最后用#结束输入 显示结果时先显示所转化成的逆波兰式,然后是结果
java 逆波兰式 (这个是java版的 还附有实验报告)
源代码 博文链接:https://leon-a.iteye.com/blog/186104
1.本例是对数据结构栈的练习 2.本例使用了java类集作为辅助,但不是必要,所有功能都可以自己实现 3.本例有输入四则运算的合法性判断方法,是基于逻辑实现,可以使用正则表达式字符匹配,会是代码简洁不少.
逆波兰算法的java版,能够将运算字符串转换为逆波兰式,并尽心简单的错误判断处理!
逆波兰式的翻译和计算。编译原理的实验报告,有利于新手对于逆波兰的基础理解。文件中给出了具体的代码和理解,还有结果截图显示。采用C语言编写,简单易懂。就一个实验报告!!
这是一个支持浮点数计算的计算器,主要运用了逆波兰法的方式,输入中辍表达式即可计算,有容错机制,比如--,**,-)等等错误输入方式的容错,还有输入字母的容错
借助了逆波兰式解决表达式求值问题~~c++源码~~数据结构课程设计
NULL 博文链接:https://mingjian01.iteye.com/blog/748154
这是严蔚敏《数据结构》配套习题册上的题目:将逆波兰式转换成波兰式,并提示错误(作为简化,只处理"+-*/"和0~9的数字)。 例如:"123*-"转换成波兰式为"-1*23" 逆波兰式"123*-"的表达式树如下: 所以这个转换...