Вступление
Написание оценщика выражений, каким бы простым оно ни было, всегда было для меня давней проблемой, главным образом потому, что это кажется таким простым, и все же очень быстро становится сложным.
Написать код для анализа и вычисления простого выражения с несколькими операндами и/или операторами с одинаковым приоритетом очень просто. Однако обобщение на более высокие сложности может быть действительно сложным из-за множества факторов: приоритета операторов, вложенности выражений и круглых скобок.
Вдохновленный первой главой того, что обещает быть удивительным прочтением книги: “Разработка компилятора”, 2-е издание, и, взяв только их простые определения синтаксического анализатора и сканера, мне удалось собрать небольшой пример, который кажется достаточно хорошим, чтобы поделиться.
Разработка языка для обсуждения математических выражений
Первое, что нам нужно определить при написании чего-то подобного, – это язык, который хорошо переводится в код, что позволяет нам думать о проблеме на более высоком уровне абстракции.
Мы скажем, что выражение состоит из токенов, или, как я это назвал, TokenType s.
public enum TokenType {
ADD,
SUB,
MUL,
DIV,
POW,
LPAR,
RPAR,
VALUE;
@Override
public String toString() {
switch (this.ordinal()){
case 0:
return "+";
case 1:
return "-";
case 2:
return "*";
case 3:
return "/";
case 4:
return "^";
case 5:
return "(";
case 6:
return ")";
case 7:
return this.name();
default:
return "null";
}
}
public static TokenType fromString(String s){
switch (s){
case "+":
return TokenType.ADD;
case "-":
return TokenType.SUB;
case "*":
return TokenType.MUL;
case "/":
return TokenType.DIV;
case "^":
return TokenType.POW;
case "(":
return TokenType.LPAR;
case ")":
return TokenType.RPAR;
default:
return TokenType.VALUE;
}
}
}
Это простое перечисление Java с методами для записи из/в строки в токены и наоборот.
Мы сразу же замечаем, что . для десятичных значений кодируется в перечислении как “значение”, поскольку это не специальный токен. Очевидно, что это можно улучшить и дальше, но на данный момент кажется достаточно хорошим.
Итак, с этого момента, когда мы будем говорить о математическом выражении, мы будем говорить о нем в терминах его TokenType s.
Написание и понимание сканера
Сканер – это часть интерфейса компилятора, которая будет считывать выражение и сопоставлять его части с известными токенами, чтобы выражение могло иметь реальное значение в контексте, в котором мы будем его оценивать.
Начиная с простого выражения, такого как 12+5 , после прохождения сканера, мы могли бы получить вывод по строкам:
(12, Жетон. ЧИСЛО), (+, Маркер. ДОБАВИТЬ), (5, Токен. ЧИСЛО)
Это позволит нам взглянуть на выражение и проанализировать его, оценить, привести к более простой форме и т.д.
При первом проходе сканера некоторые вещи необходимо будет исправить, например, если мы увидим выражение:
(-, Жетон. SUB), (3, Жетон. ЧИСЛО) , то, что мы действительно хотим иметь, это: (-3, Жетон. ЧИСЛО) .
Я решил сделать это дальше по конвейеру, на этапе синтаксического анализа.
Код для сканера выглядит следующим образом:
public class ScannedToken {
private String expressionPiece;
private TokenType type;
public ScannedToken(String exp, TokenType type){
this.expressionPiece = exp;
this.type = type;
}
@Override
public String toString(){
return "(Expr:"+ expressionPiece+ ", Token:"+ type+")";
}
public TokenType type(){
return type;
}
public String expression(){
return expressionPiece;
}
}
A Отсканированный токен – это токен, помеченный типом токена, который мы будем использовать при выполнении фактического сканирования выражений.
Код для сканера выглядит следующим образом:
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class Scanner {
private final String expression;
public Scanner(String expr) {
this.expression = expr;
}
public List scan() {
StringBuilder value = new StringBuilder();
List scannedExpr = new ArrayList<>();
for (char c : expression.toCharArray()) {
TokenType type = TokenType.fromString(new String(new char[] {c}));
if (!type.equals(TokenType.VALUE)) {
if (value.length() > 0) {
//Add the full value TOKEN
ScannedToken st = new ScannedToken(value.toString(), TokenType.VALUE);
scannedExpr.add(st);
}
value = new StringBuilder(new String(new char[] {c}));
ScannedToken st = new ScannedToken(value.toString(), type);
scannedExpr.add(st);
value = new StringBuilder();
} else {
value.append(new String(new char[] {c}));
}
}
if (value.length() > 0) {
//Add the full value TOKEN
ScannedToken st = new ScannedToken(value.toString(), TokenType.VALUE);
scannedExpr.add(st);
}
return scannedExpr;
}
public double evaluate(List tokenizedExpression) {
if (tokenizedExpression.size() == 1) {
return Double.parseDouble(tokenizedExpression.get(0).expression());
}
//Eval order is PEMDAS - Parenthesis, exponents, multiply, divide, add, subtract
List simpleExpr = new ArrayList<>();
int idx =
tokenizedExpression.stream()
.map(ScannedToken::type)
.collect(Collectors.toList())
.lastIndexOf(TokenType.LPAR);
int matchingRPAR = -1;
if (idx >= 0) {
for (int i = idx + 1; i < tokenizedExpression.size(); i++) {
ScannedToken curr = tokenizedExpression.get(i);
if (curr.type() == TokenType.RPAR) {
matchingRPAR = i;
break;
} else {
simpleExpr.add(tokenizedExpression.get(i));
}
}
} else {
simpleExpr.addAll(tokenizedExpression);
return evaluateSimpleExpression(tokenizedExpression);
}
double value = evaluateSimpleExpression(simpleExpr);
// System.out.println("val is " + value);
List partiallyEvaluatedExpression = new ArrayList<>();
for (int i = 0; i < idx; i++) {
partiallyEvaluatedExpression.add(tokenizedExpression.get(i));
}
partiallyEvaluatedExpression.add(new ScannedToken(Double.toString(value), TokenType.VALUE));
for (int i = matchingRPAR + 1; i < tokenizedExpression.size(); i++) {
partiallyEvaluatedExpression.add(tokenizedExpression.get(i));
}
// from idx find first ), extract, evaluate, replace, call recursively
// System.out.println("Expr to eval indexes: " + idx + ", " + matchingRPAR);
System.out.println(partiallyEvaluatedExpression);
return evaluate(partiallyEvaluatedExpression);
}
//A simple expression won't contain parenthesis
public double evaluateSimpleExpression(List expression) {
if (expression.size() == 1) {
return Double.parseDouble(expression.get(0).expression());
} else {
List newExpression = new ArrayList<>();
int idx = expression.stream().map(ScannedToken::type).collect(Collectors.toList()).indexOf(TokenType.POW);
if (idx != -1) {
double base = Double.parseDouble(expression.get(idx - 1).expression());
double exp = Double.parseDouble(expression.get(idx + 1).expression());
DecimalFormat df = new DecimalFormat(".00");
double ans = Math.pow(base, exp);
for (int i = 0; i < idx - 1; i++) {
newExpression.add(expression.get(i));
}
newExpression.add(new ScannedToken(ans + "", TokenType.VALUE));
for (int i = idx + 2; i < expression.size(); i++) {
newExpression.add(expression.get(i));
}
return evaluateSimpleExpression(newExpression);
} else {
int mulIdx = expression.stream()
.map(ScannedToken::type)
.collect(Collectors.toList())
.indexOf(TokenType.MUL);
int divIdx = expression.stream()
.map(ScannedToken::type)
.collect(Collectors.toList())
.indexOf(TokenType.DIV);
int computationIdx = (mulIdx >= 0 && divIdx >= 0) ? Math.min(mulIdx, divIdx) : Math.max(mulIdx, divIdx);
if (computationIdx != -1) {
double left = Double.parseDouble(expression.get(computationIdx - 1).expression());
double right = Double.parseDouble(expression.get(computationIdx + 1).expression());
DecimalFormat df = new DecimalFormat(".00");
double ans = computationIdx == mulIdx ? left * right : left / right * 1.0;
for (int i = 0; i < computationIdx - 1; i++) {
newExpression.add(expression.get(i));
}
newExpression.add(new ScannedToken(ans + "", TokenType.VALUE));
for (int i = computationIdx + 2; i < expression.size(); i++) {
newExpression.add(expression.get(i));
}
return evaluateSimpleExpression(newExpression);
} else {
int addIdx = expression.stream()
.map(e -> e.type())
.collect(Collectors.toList())
.indexOf(TokenType.ADD);
int subIdx = expression.stream()
.map(e -> e.type())
.collect(Collectors.toList())
.indexOf(TokenType.SUB);
int computationIdx2 = (addIdx >= 0 && subIdx >= 0) ?
Math.min(addIdx, subIdx) :
Math.max(addIdx, subIdx);
if (computationIdx2 != -1) {
double left = Double.parseDouble(expression.get(computationIdx2 - 1).expression());
double right = Double.parseDouble(expression.get(computationIdx2 + 1).expression());
DecimalFormat df = new DecimalFormat(".00");
double ans = computationIdx2 == addIdx ? left + right : (left - right) * 1.0;
for (int i = 0; i < computationIdx2 - 1; i++) {
newExpression.add(expression.get(i));
}
newExpression.add(new ScannedToken(ans + "", TokenType.VALUE));
for (int i = computationIdx2 + 2; i < expression.size(); i++) {
newExpression.add(expression.get(i));
}
return evaluateSimpleExpression(newExpression);
}
}
}
}
return -1.0;
}
}
Код для сканера немного слишком запутан, но основная идея состоит в том, чтобы посмотреть на выражение и оценить его так, как это сделал бы математик-человек:
Мы ищем самую внутреннюю скобку, извлекаем ее внутреннее выражение и считаем ее Простое выражение . Таким образом, простое выражение – это выражение без скобок.
Простое выражение может быть вычислено напрямую, с помощью рекурсии, в соответствии с правилом PEMDAS: Сначала скобки, затем показатели, затем умножение и деление в порядке их появления, а затем вычитание и сложение в порядке их появления.
После вычисления простых выражений результирующий токен заменяется в исходном выражении и рекурсивно передается для повторного вычисления, пока конечным результатом не станет один токен с одним значением.
И это основная идея.
Добавление анализатора, чтобы избежать проблем с “неполными” токенами
Очевидно, что то, как это реализовано сейчас, все еще неполно, как с точки зрения обработки ошибок, так и с точки зрения неправильно маркированных выражений. Обработка ошибок не была выполнена, поэтому такие вещи, как неполные выражения или несбалансированные скобки, либо приведут процесс в цикл, либо просто завершатся сбоем. Чтобы сделать это позже:)
Что нам нужно сделать сейчас в анализаторе, чтобы получить простое решение, это решить, когда мы можем создать токен с отрицательным числом из пары токенов. ВСПОМОГАТЕЛЬНЫЙ и символический. ценность.
Крайних случаев существует два:
если Знак. ВСПОМОГАТЕЛЬНЫЙ и символический. ЗНАЧЕНИЕ находится в начале выражения, затем мы создаем один токен с отрицательным значением;
если эти два токена находятся сразу после открывающей скобки, они являются частью начала сложного выражения, и в этом случае нам также необходимо их объединить;
Это то, что мы делаем в синтаксическом анализаторе:
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class Parser {
private final List expression;
public Parser(List expression) {
this.expression = expression;
}
/*
We need a triple in a sliding window fashion where middle is current token so we can contextualize what
needs to be parsed into correct tokens
*/
public List parse() {
TokenType prev = null;
TokenType curr = null;
TokenType next = null;
List properlyParsedExpression = new ArrayList<>();
List types = expression.stream().map(ScannedToken::type).collect(Collectors.toList());
List indexes = new ArrayList<>();
List negativeValues = new ArrayList<>();
for (int i = 0; i < types.size() - 1; i++) {
prev = i == 0 ? null : types.get(i - 1);
curr = types.get(i);
next = types.get(i + 1);
if (prev == null && curr == TokenType.SUB && next == TokenType.VALUE) {
ScannedToken negativeValue =
new ScannedToken("" + (-1 * Double.parseDouble(expression.get(i + 1).expression())),
TokenType.VALUE);
System.out.println("new token at index " + i);
indexes.add(i);
negativeValues.add(negativeValue);
} else if (prev == TokenType.LPAR && curr == TokenType.SUB && next == TokenType.VALUE) {
ScannedToken negativeValue =
new ScannedToken("" + (-1 * Double.parseDouble(expression.get(i + 1).expression())),
TokenType.VALUE);
System.out.println("new token at index " + i);
indexes.add(i);
negativeValues.add(negativeValue);
}
}
int maxIterations = expression.size();
int i = 0;
int j = 0;
while (i < maxIterations) {
if (indexes.contains(i) && j < negativeValues.size()) {
properlyParsedExpression.add(negativeValues.get(j));
j++;
i++;
}
else {
properlyParsedExpression.add(expression.get(i));
}
i++;
}
System.out.println(properlyParsedExpression);
return properlyParsedExpression;
}
}
И, наконец, основная функция нашего кода, где мы выполняем то, что мы сделали:
import java.util.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException{
System.out.println("Enter a mathematical expression");
//Enter data using BufferReader
while(true){
BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
// Reading data using readLine
String name = reader.readLine();
Scanner sc = new Scanner(name);
//(12*5)+1*(8.6-3*2^2)-34
//(12*5)
//12*5
//12
//-5+12*(-3+2)
//-12
//12
//15/(3+2)
List scanExp = sc.scan();
Parser parser = new Parser(scanExp);
List parsed = parser.parse();
scanExp.forEach(e->System.out.println(e));
System.out.println(sc.evaluate(parsed));
}
}
}
Итак, мы оцениваем проанализированное выражение с исправленными токенами и получаем желаемое значение.
Дополнительные конструктивные соображения
Существует множество дополнительных конструктивных соображений, которые могут улучшить это:
Обработка ошибок отсутствует, поэтому, если есть недопустимое выражение, сканер просто умрет с исключением stackoverflow или outOfBounds;
Анализатор должен быть более надежным, чтобы корректно обрабатывать неправильные входные данные;
Очевидно, что это подход, который имитирует то, как человек будет оценивать выражение, и правила грамматики, которые по сути являются правилами приоритета операций, все закодированы в
Сканерекод, следуя правилу PEMDAS программно ; В реальной реализации мы можем назначить, например, значения приоритета операторам и построить дерево, учитывающее эти прецеденты, возможно, делегировав этот шаг синтаксическому анализатору, а затем оценить выражение так же просто, как выполнить обход дерева по порядку по значениям приоритета, рекурсивно оценивая подвыражения;
Вывод
Это было отличное упражнение, и я думаю, что это хороший вызов, который может принять каждый! Это показывает, как то, что обманчиво просто, на самом деле может быть довольно сложным и это унизительное упражнение! В качестве рекомендуемого чтения, из которого я черпал вдохновение для написания этого, я рекомендую 2-е издание книги “Разработка компилятора”.
Оригинал: “https://dev.to/brunooliveira/writing-a-mathematical-expression-evaluator-in-java-1ka6”