编写程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。
例如给定表达式： 1 + 2 ）* 3 - 4 ）* 5 - 6 ) ) )
程序可以输出：（（1 + 2 ）*（（3 - 4）*（5 - 6）））
并计算结果，Java代码如下：
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 '+':
return left.add(right);
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))) {
exprList.add(new CalculateNode(CalculateNode.OPERAND, "0"));
}
lastNode = node;
// 运算数直接加入结果队列
if (node.type == CalculateNode.OPERAND) {
exprList.add(node);
} 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;
}
exprList.add(topNode);
}
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;
}
exprList.add(topNode);
stack.pop();
}
stack.push(node);
}
}
}
while (!stack.empty()) {
if ("(".equals(stack.peek().value)) {
throw new RuntimeException("ParenthesisMismatchException");
}
exprList.add(stack.pop());
}
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));
}
}
本文链接：http://bookshadow.com/weblog/2014/02/28/expr-eval/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
