## 表达式括号补全与求值 作者是 在线疯狂 发布于 2014年2月28日 .

``````
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
* 表达式求值
*
* @author 在线疯狂
*/
public class ExpressionUtils {

private static int getPriority(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}

private static BigDecimal calculate(BigDecimal left, BigDecimal right,
char operator) {
switch (operator) {
case '+':
case '-':
return left.subtract(right);
case '*':
return left.multiply(right);
case '/':
return left.divide(right, 4, BigDecimal.ROUND_HALF_UP);// 四舍五入保留4位小数
default:
return null;
}
}

/**
* 表达式求值<br>
* 支持+,-,×,÷和括号四则运算
*
* @param expression
* @return
*/
public static BigDecimal getValue(String expression) {
// 过滤表达式中可能存在的空格或者制表符
expression = expression.replace(" ", "").replace("\t", "");
List<CalculateNode> nodeList = getSuffixExpression(expression);
Stack<BigDecimal> stack = new Stack<BigDecimal>();
for (CalculateNode node : nodeList) {

if (node.type == CalculateNode.OPERAND) {
stack.push(new BigDecimal(node.value));
} else {
BigDecimal right = stack.pop();
BigDecimal left = stack.pop();
stack.push(calculate(left, right, node.value.charAt(0)));
}

}
BigDecimal ans = stack.pop();
if (!stack.empty()) {
throw new RuntimeException("InvalidExpressionException");
}
return ans;
}

/**
* 修复缺左括号的中缀表达式
* @param expression
* @return
*/
public static String repairExpression(String expression) {
Stack<String> resultStack = new Stack<String>();
expression = expression.replace(" ", "").replace("\t", "");
char[] chArr = expression.toCharArray();
// 运算符栈
Stack<CalculateNode> operatorStack = new Stack<CalculateNode>();

for (int i = 0; i < chArr.length;) {
CalculateNode node = new CalculateNode();
i = getNextCalculateNode(i, chArr, node);
// 如果是运算数，直接加入结果栈
if (node.type == CalculateNode.OPERAND) {
resultStack.push(node.value);
} else {
// 是运算符
if ("(".equals(node.value)) {
// 忽略左括号
} else if (")".equals(node.value)) {
CalculateNode topOperator = operatorStack.isEmpty() ? null : operatorStack.pop();
if (topOperator != null) {
String rightOperand = resultStack.pop();
String leftOperand = resultStack.pop();
resultStack.push("(" + leftOperand + " " + topOperator.value + " " + rightOperand + ")");
} else {
String operand = resultStack.pop();
resultStack.push("(" + operand + ")");
}
} else {
operatorStack.push(node);
}
}
}
while (!operatorStack.isEmpty()) {
CalculateNode topOperator = operatorStack.pop();
String rightOperand = resultStack.pop();
String leftOperand = resultStack.pop();
resultStack.push(leftOperand + " " + topOperator.value + " " + rightOperand);
}
return resultStack.pop();
}

/**
* 由中缀表达式求后缀表达式
* @param expression
* @return
*/
public static List<CalculateNode> getSuffixExpression(String expression) {
List<CalculateNode> exprList = new ArrayList<CalculateNode>();
char[] chArr = expression.toCharArray();
// 判断表达式中是否包含非法字符
for (char ch : chArr) {
if (!isValidChar(ch)) {
throw new RuntimeException("InvalidCharacterException");
}
}
// 运算符栈
Stack<CalculateNode> stack = new Stack<CalculateNode>();
CalculateNode lastNode = null;
for (int i = 0; i < chArr.length;) {
CalculateNode node = new CalculateNode();
i = getNextCalculateNode(i, chArr, node);
// 将+/-号前插入数字0
if ((lastNode == null || "(".equals(lastNode.value))
&& ("-".equals(node.value) || "+".equals(node.value))) {
}
lastNode = node;
// 运算数直接加入结果队列
if (node.type == CalculateNode.OPERAND) {
} else {
// 是运算符
if ("(".equals(node.value)) {
stack.push(node);
} else if (")".equals(node.value)) {
// 右括号弹栈直到遇到第一个左括号为止
boolean isMatch = false;
while (!stack.empty()) {
CalculateNode topNode = stack.pop();
if ("(".equals(topNode.value)) {
isMatch = true;
break;
}
}
if (!isMatch) {
throw new RuntimeException(
"ParenthesisMismatchException");
}
} else {
while (!stack.empty()) {
CalculateNode topNode = stack.peek();
if ("(".equals(topNode.value)) {
break;
}
if (getPriority(topNode.value.charAt(0)) < getPriority(node.value
.charAt(0))) {
break;
}
stack.pop();
}
stack.push(node);
}
}
}
while (!stack.empty()) {
if ("(".equals(stack.peek().value)) {
throw new RuntimeException("ParenthesisMismatchException");
}
}
return exprList;
}

/**
* 获取下一个计算节点
*
* @param loc
*    当前位置
* @param chArr
*    表达式字符数组
* @param node
*    会修改传入节点的值
* @return 下一个节点在字符数组中的位置
*/
public static int getNextCalculateNode(int loc, char chArr[],
CalculateNode node) {
char firstChar = chArr[loc];
int idx = loc + 1;
if (isOperator(firstChar)) {
node.type = CalculateNode.OPERATOR;
node.value = firstChar + "";
} else {
node.type = CalculateNode.OPERAND;
StringBuffer sb = new StringBuffer();
sb.append(firstChar);
while (idx < chArr.length && !isOperator(chArr[idx])) {
sb.append(chArr[idx++]);
}
node.value = sb.toString();
if (".".equals(node.value)) {
node.value = "0";
}
if (node.value.indexOf('.') != node.value.lastIndexOf('.')) {
throw new RuntimeException("InvalidOperandException");
}
}
return idx;
}

private static class CalculateNode {
public static final int OPERAND = 0;
public static final int OPERATOR = 1;
// 计算节点类型,0表示操作数,1表示运算符
private int type;
// 节点值
private String value;

public CalculateNode() {
}

public CalculateNode(int type, String value) {
this.type = type;
this.value = value;
}

@Override
public String toString() {
return "{" + (type == OPERAND ? "[OPERAND]" : "[OPERATOR]") + value
+ "}";
}
}

/**
* 判断某字符是否为合法字符(数字,小数点,运算符或者括号)
* @param ch
* @return
*/
public static boolean isValidChar(char ch) {
if (ch >= '0' && ch <= '9')
return true;
if (ch == '.')
return true;
if (isOperator(ch))
return true;
return false;
}

private static boolean isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '('
|| ch == ')';
}

public static void main(String args[]) throws Exception {
//String brokenExp = "3.45 + 2) * 2 + 4)";
String brokenExp = "(1 + 2) * (3 + 4) / 5 + 6 * 8 - (10.1 * 2) * ((1 + 2) * 4)".replace("(", "");
String exp = repairExpression(brokenExp);
System.out.println("缺括号表达式: " + brokenExp);
System.out.println("修复后表达式: " + exp);
System.out.println("表达式求值: " + getValue(exp));
}

}
``````

Pingbacks已关闭。