Настройка строк сводилась к перечислению групп объектов, операции которых должны были участвовать в вычислении значения строки. Со столбцами ситуация обстояла сложнее - здесь нужно было задать правила вычисления.
Т. к. значения по столбцам должны были вычисляться на основании полей операций, значений по другим столбцам, а также могли умножаться и делиться на число, я решил сделать правило столбца в виде обычного математического выражения типа String. Естественно, встала проблема разбора выражения и вычисления его значения.
В этом топике хотелось бы поделиться опытом приведения выражения к Обратной польской нотации и вычисления результата на ее основании.
Теория с примерами достаточно неплохо изложена в Википедии. Неплохая английская статья с анимацией работы алгоритма лежит здесь.
Здесь я отброшу специфику моей задачи и приведу свою реализацию описанных алгоритмов для разбора выражения, содержащего числа с плавающей точкой, четыре основных математических операнда и скобки.
import java.math.BigDecimal; import java.util.*; /** * Класс содержит утилиты для разбора и обработки математических выражений. * * @author Борис Марченко * @version $Revision$ $Date$ */ public class ExpressionUtils { /** * Основные математические операции и их приоритеты. * * @see #sortingStation(String, java.util.Map) */ public static final Map<String, Integer> MAIN_MATH_OPERATIONS; static { MAIN_MATH_OPERATIONS = new HashMap<String, Integer>(); MAIN_MATH_OPERATIONS.put("*", 1); MAIN_MATH_OPERATIONS.put("/", 1); MAIN_MATH_OPERATIONS.put("+", 2); MAIN_MATH_OPERATIONS.put("-", 2); } /** * Преобразует выражение из инфиксной нотации в обратную польскую нотацию (ОПН) по алгоритму <i>Сортировочная * станция</i> Эдскера Дейкстры. Отличительной особенностью обратной польской нотации является то, что все * аргументы (или операнды) расположены перед операцией. Это позволяет избавиться от необходимости использования * скобок. Например, выражение, записаное в инфиксной нотации как 3 * (4 + 7), будет выглядеть как 3 4 7 + * * в ОПН. Символы скобок могут быть изменены. * <a href="http://ru.wikipedia.org/wiki/Обратная_польская_запись">Подробнее об ОПЗ</a>. * * @param expression выражение в инфиксной форме. * @param operations операторы, использующиеся в выражении (ассоциированные, либо лево-ассоциированные). * Значениями карты служат приоритеты операции (самый высокий приоритет - 1). Например, для 5 * основных математических операторов карта будет выглядеть так: * <pre> * * -> 1 * / -> 1 * + -> 2 * - -> 2 * </pre> * Приведенные операторы определены в константе {@link #MAIN_MATH_OPERATIONS}. * @param leftBracket открывающая скобка. * @param rightBracket закрывающая скобка. * @return преобразованное выражение в ОПН. */ public static String sortingStation(String expression, Map<String, Integer> operations, String leftBracket, String rightBracket) { if (expression == null || expression.length() == 0) throw new IllegalStateException("Expression isn't specified."); if (operations == null || operations.isEmpty()) throw new IllegalStateException("Operations aren't specified."); // Выходная строка, разбитая на "символы" - операции и операнды.. List<String> out = new ArrayList<String>(); // Стек операций. Stack<String> stack = new Stack<String>(); // Удаление пробелов из выражения. expression = expression.replace(" ", ""); // Множество "символов", не являющихся операндами (операции и скобки). Set<String> operationSymbols = new HashSet<String>(operations.keySet()); operationSymbols.add(leftBracket); operationSymbols.add(rightBracket); // Индекс, на котором закончился разбор строки на прошлой итерации. int index = 0; // Признак необходимости поиска следующего элемента. boolean findNext = true; while (findNext) { int nextOperationIndex = expression.length(); String nextOperation = ""; // Поиск следующего оператора или скобки. for (String operation : operationSymbols) { int i = expression.indexOf(operation, index); if (i >= 0 && i < nextOperationIndex) { nextOperation = operation; nextOperationIndex = i; } } // Оператор не найден. if (nextOperationIndex == expression.length()) { findNext = false; } else { // Если оператору или скобке предшествует операнд, добавляем его в выходную строку. if (index != nextOperationIndex) { out.add(expression.substring(index, nextOperationIndex)); } // Обработка операторов и скобок. // Открывающая скобка. if (nextOperation.equals(leftBracket)) { stack.push(nextOperation); } // Закрывающая скобка. else if (nextOperation.equals(rightBracket)) { while (!stack.peek().equals(leftBracket)) { out.add(stack.pop()); if (stack.empty()) { throw new IllegalArgumentException("Unmatched brackets"); } } stack.pop(); } // Операция. else { while (!stack.empty() && !stack.peek().equals(leftBracket) && (operations.get(nextOperation) >= operations.get(stack.peek()))) { out.add(stack.pop()); } stack.push(nextOperation); } index = nextOperationIndex + nextOperation.length(); } } // Добавление в выходную строку операндов после последнего операнда. if (index != expression.length()) { out.add(expression.substring(index)); } // Пробразование выходного списка к выходной строке. while (!stack.empty()) { out.add(stack.pop()); } StringBuffer result = new StringBuffer(); if (!out.isEmpty()) result.append(out.remove(0)); while (!out.isEmpty()) result.append(" ").append(out.remove(0)); return result.toString(); } /** * Преобразует выражение из инфиксной нотации в обратную польскую нотацию (ОПН) по алгоритму <i>Сортировочная * станция</i> Эдскера Дейкстры. Отличительной особенностью обратной польской нотации является то, что все * аргументы (или операнды) расположены перед операцией. Это позволяет избавиться от необходимости использования * скобок. Например, выражение, записаное в инфиксной нотации как 3 * (4 + 7), будет выглядеть как 3 4 7 + * * в ОПН. * <a href="http://ru.wikipedia.org/wiki/Обратная_польская_запись">Подробнее об ОПЗ</a>. * * @param expression выражение в инфиксной форме. * @param operations операторы, использующиеся в выражении (ассоциированные, либо лево-ассоциированные). * Значениями карты служат приоритеты операции (самый высокий приоритет - 1). Например, для 5 * основных математических операторов карта будет выглядеть так: * <pre> * * -> 1 * / -> 1 * + -> 2 * - -> 2 * </pre> * Приведенные операторы определены в константе {@link #MAIN_MATH_OPERATIONS}. * @return преобразованное выражение в ОПН. */ public static String sortingStation(String expression, Map<String, Integer> operations) { return sortingStation(expression, operations, "(", ")"); } /** * Вычисляет значение выражения, записанного в инфиксной нотации. Выражение может содержать скобки, числа с * плавающей точкой, четыре основных математических операндов. * * @param expression выражение. * @return результат вычисления. */ public static BigDecimal calculateExpression(String expression) { String rpn = sortingStation(expression, MAIN_MATH_OPERATIONS); StringTokenizer tokenizer = new StringTokenizer(rpn, " "); Stack<BigDecimal> stack = new Stack<BigDecimal>(); while (tokenizer.hasMoreTokens()) { String token = tokenizer.nextToken(); // Операнд. if (!MAIN_MATH_OPERATIONS.keySet().contains(token)) { stack.push(new BigDecimal(token)); } else { BigDecimal operand2 = stack.pop(); BigDecimal operand1 = stack.empty() ? BigDecimal.ZERO : stack.pop(); if (token.equals("*")) { stack.push(operand1.multiply(operand2)); } else if (token.equals("/")) { stack.push(operand1.divide(operand2)); } else if (token.equals("+")) { stack.push(operand1.add(operand2)); } else if (token.equals("-")) { stack.push(operand1.subtract(operand2)); } } } if (stack.size() != 1) throw new IllegalArgumentException("Expression syntax error."); return stack.pop(); } /** * Закрытый конструктор класса. */ private ExpressionUtils() { } /** * Тестирует методы. * * @param args список аргументов командной строки. */ public static void main(String[] args) { String expression = "3 + 4 * 2 / (1 - 5) + 2"; System.out.println("Инфиксная нотация: " + expression); System.out.println("\tРезультат 3"); String rpn = sortingStation(expression, MAIN_MATH_OPERATIONS); System.out.println("Обратная польская нотация: " + rpn); System.out.println("\tРезультат " + calculateExpression(expression)); } } /* $Log: $ */
Результат:
Инфиксная нотация: 3 + 4 * 2 / (1 - 5) + 2 Результат 3 Обратная польская нотация: 3 4 2 * 1 5 - / + 2 + Результат 3