import java.util.*;
/**
* Created by threetwo on 17/3/23.
*/
public class Calculator {
/**
* opd: 运算数
* ops: 运算符
*/
private static final int TYPE_OPD = 0;
private static final int TYPE_OPS = 1;
/* 运算符原始优先级映射 */
private static final Map<String, Integer> opsPriority = new HashMap<>();
/* 运算符中优先级最大的数值*/
private static int maxPriority;
static {
opsPriority.put("+", 1);
opsPriority.put("-", 1);
opsPriority.put("*", 2);
opsPriority.put("/", 2);
maxPriority = opsPriority.values().stream().max(Integer::compareTo).get();
}
/**
* opsList: 运算符结点列表
* last: 最新添加的结点，便于添加新的结点
* base: 变动的优先级值，随着左括号的出现增加，右括号的出现减少
* mathExpression: 字符串形式的数学表达式，目前只支持 加减乘除，小括号
* result: 数学表达式的值
*/
private List<Node> opsList = new ArrayList<>();
private Node last = null;
private int base = 0;
private String mathExpression;
private Double result = null;
private class Node{
int type;
double value;
int priority;
String ops;
Node prev;
Node next;
public Node(int type, String ops){
this.type = type;
this.ops = ops;
this.priority = opsPriority.get(ops);
}
public Node(int type, double value){
this.type = type;
this.value = value;
}
}
public Calculator(String mathExpression){
this.mathExpression = mathExpression;
parseExpression(this.mathExpression);
}
/**
* 添加操作数结点
* @param value: 操作数结点的值
* @return 刚添加的结点
*/
private Node addOpdNode(double value){
Node opdNode = new Node(TYPE_OPD, value);
if (last == null){
last = opdNode;
}else{
last.next = opdNode;
opdNode.prev = last;
last = opdNode;
}
return opdNode;
}
/**
* 添加运算符结点
* @param ops: 运算符
* @return 刚添加的结点
*/
private Node addOpsNode(String ops){
Node opsNode = new Node(TYPE_OPS, ops);
opsNode.priority = base + opsPriority.get(ops);
last.next = opsNode;
opsNode.prev = last;
last = opsNode;
return opsNode;
}
/**
* 字符串形式的数学表达式解析成为元素具有优先级的链表
* @param expression: 数学表达式。操作数，运算符，括号必须使用一个空格作为分隔符，例：1 + 2 * ( 3 - 4 )
*/
private void parseExpression(String expression) {
String[] parts = expression.split(" ");
for (int i = 0; i < parts.length; i++) {
String c = parts[i];
if(c.equals("(")){
base += maxPriority;
}else if(c.equals(")")){
base -= maxPriority;
}else if(Character.isDigit(c.charAt(0))){
addOpdNode(Double.parseDouble(c));
}else{
Node opsNode = addOpsNode(c);
opsList.add(opsNode);
}
}
}
/**
* 将字符串形式的数学表达式解析成为链表(其中的元素具有优先级)
* @param expression: 数学表达式。操作数，运算符，括号是否使用空格作为分隔符无所谓
*/
private void parseExpressionWithPerCharacter(String expression) {
// 目前解析出的值
double value = 0;
// 记录目前已知有多少位小数
int count = 0;
// 如果出现小数点则是浮点数
boolean isFloat = false;
// 是否已经存在解析出的值，在添加结点后置为false，若出现数字字符置为true
boolean hasValue = false;
String[] parts = expression.split(" ");
// 对字符串形式的数学表达式一个一个字符的解析
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if(c == '('){
base += 2;
}else if(c == ')'){
if (hasValue){
addOpdNode(value);
hasValue = false;
value = 0;
}
base -= 2;
}else if(c == '.'){
isFloat = true;
}else if(Character.isDigit(c)){
hasValue = true;
int n = Integer.parseInt(Character.toString(c));
if (isFloat){
value = value + n * Math.pow(10, -(++count));
}else{
value = value * 10 + n;
}
}else if(c == ' '){
continue;
}else{
if (hasValue){
addOpdNode(value);
value = 0;
}
Node opsNode = addOpsNode(Character.toString(c));
opsList.add(opsNode);
isFloat = false;
count = 0;
hasValue = false;
}
}
if (hasValue){
addOpdNode(value);
}
}
/**
* 依据运算符类型执行双目运算
* @param ops: 双目运算符
* @param leftOpd: 左操作数
* @param rightOpd: 右操作数
* @return 运算结果
*/
private static double doOps(String ops, double leftOpd, double rightOpd){
if(ops.equals("+")){
return leftOpd + rightOpd;
}else if(ops.equals("-")){
return leftOpd - rightOpd;
}else if(ops.equals("*")){
return leftOpd * rightOpd;
}else if(ops.equals("/")){
return leftOpd / rightOpd;
}
return 0;
}
/**
* 执行指定的运算符结点的运算
* @param ops: 需要执行运算的运算符结点
*/
private static void apply(Node ops){
Node arg1Node = ops.prev;
Node arg2Node = ops.next;
ops.value = doOps(ops.ops, arg1Node.value, arg2Node.value);
if(arg1Node.prev != null){
arg1Node.prev.next = ops;
}
if(arg2Node.next != null){
arg2Node.next.prev = ops;
}
ops.prev = arg1Node.prev;
ops.next = arg2Node.next;
}
/**
* 获取表达式的结果
* @return
*/
public double getResult(){
if (result != null){
return result;
}
// 将运算符结点列表按照优先级从高到低排序
opsList.sort((n1, n2)->{
if(n1.priority > n2.priority)
return -1;
if(n1.priority < n2.priority)
return 1;
else
return 0;
});
// 执行每一个运算符结点的运算
for(Node ops: opsList){
apply(ops);
}
// 最终结果就在最后执行运算的运算符结点中
Node resultNode = opsList.get(opsList.size()-1);
result = resultNode.value;
return result;
}
/**
* 获取数学表达式
* @return
*/
public String getMathExpression(){
return this.mathExpression;
}
public static void main(String[] args) {
Calculator calculator = new Calculator("( ( 1.1 * 3 ) ) / 1 + 2");
System.out.println(calculator.getResult());
}
}
网友评论