Eu ainda era um estudante quando caí nas mãos do livro "Curso para iniciantes C e C ++" da editora Dialog MIFI. Foi a partir deste livro que aprendi sobre os conceitos básicos da programação orientada a objetos e também me trouxe um problema que não consegui resolver por um bom tempo. No final, havia uma aplicação listando programas, um dos quais era chamado de calculadora recursiva. Este foi o meu primeiro encontro com a análise de expressões aritméticas usando o método de descida recursiva. Ainda me lembro daquelas longas horas que foram gastas tentando entender pelo menos algo neste código.O artigo é destinado principalmente para aqueles que enfrentam a tarefa de analisar expressões pela primeira vez.E assim, antes de escrever o analisador de expressões aritméticas, precisamos entender a estrutura dessas mesmas expressões. Por simplicidade, não consideraremos a operação menos unária e a possibilidade de usar funções na expressão por enquanto.Para descrever a estrutura, usamos as formas de Beckus-NaurE -> T + E | T - E T
T -> F * T | F / t F
F -> N | (E)
Aqui está a barra vertical "|" significa uma operação lógica "ou" e E, T, F, N - vários tipos de subexpressões nas quais a expressão original será dividida ao usar essas frases. N neste caso indica um número.A primeira frase significa que uma expressão do tipo E pode consistir em uma expressão do tipo T mais uma expressão do tipo E, ou uma expressão do tipo T menos uma expressão do tipo E ou apenas uma expressão do tipo T.Para a segunda frase, tudo é semelhante, mas em vez de adicionar e subtrair haverá multiplicação e divisão.A terceira frase significa que uma expressão do tipo F é um número ou uma expressão do tipo E entre colchetes.Vamos tentar aplicar essas três frases a um exemplo de expressão aritmética2 + 3 * (4-5) + 6-7
Aplicamos a primeira frase várias vezesE (2 + 3 * (4-5) + 6-7) ->
T (2) + E (3 * (4-5) + 6-7) ->
T (2) + T (3 * (4-5)) + E (6-7) ->
T (2) + T (3 * (4-5)) + T (6) - T (7)
Agora nossa expressão consiste apenas em subexpressões do tipo T, então aplicamos a segunda sentença a cada uma delas.T (2) -> F (2)
T (3 * (4-5)) -> F (3) * T ((4-5)) -> F (3) * F ((4-5))
T (6) -> F (6)
T (7) -> F (7)
É hora da terceira fraseF (2) -> N (2) -> 2
F (3) -> N (3) -> 3
F ((4-5)) -> E (4-5)
F (6) -> N (6) -> 6
F (7) -> N (7) -> 7
Para a expressão entre colchetes (4-5), passamos recursivamente para a primeira frase e teremos que repetir todas as ações por analogia com a maneira como foi para o restante da expressão. Se a expressão continha colchetes aninhados, haveria mais transições recursivas. Eu recomendo que você tente aplicar independentemente as três frases a uma expressão que contenha níveis aninhados de colchetes, por exemplo 2 + 2 * (3 + 4 * (5-6)), para garantir que eles funcionem também.Agora, apenas precisamos implementar as ações que são realizadas pelas propostas na forma de código. Essa será a análise da expressão usando o método descendente recursivo, mas antes de começar a escrever o código, vamos simplificar um pouco as frases, eliminando a recursão nos dois primeiros.Se substituirmos infinitamente a primeira frase por si mesma, obteremosE -> T ± T ± T ± T ± ... ± T
A segunda frase pode ser transformada de maneira semelhante.T -> F * / F * / F * / * / ... * / F
De fato, isso significa que, em vez de recursão, podemos usar um loop aqui. Da mesma forma, a recursão não pode ser excluída da terceira frase.Vamos escrever o código em Java, porque Essa é a linguagem de programação mais familiar para mim no momento. A última observação antes de começarmos a escrever o código - deixo de fora a tarefa de tokenização, ou seja, dividindo a expressão em elementos significativos indivisíveis (tokens). Tais tokens são números, sinais de operações aritméticas e colchetes. Suponha que já tenhamos uma matriz de token como entrada da expressão.String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};
Crie a próxima classe de analisador que conterá os métodos- parse () começa a analisar uma expressão
- expression () para manipular expressões do tipo E
- term () para processar expressões do tipo T
- factor () para processar expressões do tipo F e N
public class RecursiveDescentParser {
private final String[] tokens;
private int pos = 0;
public RecursiveDescentParser(String[] tokens) {
this.tokens = tokens;
}
public Double parse() {
Double result = expression();
if (pos != tokens.length) {
throw new IllegalStateException("Error in expression at " + tokens[pos]));
}
return result;
}
private Double expression() {
Double first = term();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("+") && !operator.equals("-")) {
break;
} else {
pos++;
}
Double second = term();
if (operator.equals("+")) {
first += second;
} else {
first -= second;
}
}
return first;
}
private Double term() {
Double first = factor();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("*") && !operator.equals("/")) {
break;
} else {
pos++;
}
Double second = factor();
if (operator.equals("*")) {
first *= second;
} else {
first /= second;
}
}
return first;
}
private Double factor() {
String next = tokens[pos];
Double result;
if (next.equals("(")) {
pos++;
result = expression();
String closingBracket;
if (pos < tokens.length) {
closingBracket = tokens[pos];
} else {
throw new IllegalStateException("Unexpected end of expression");
}
if (pos < tokens.length && closingBracket.equals(")")) {
pos++;
return result;
}
throw new IllegalStateException("')' expected but " + closingBracket);
}
pos++;
return Double.parseDouble(next);
}
}
Isso é tudo. Se desejado, esse analisador pode ser ensinado a trabalhar com menos ou funções unárias em uma expressão. A primeira coisa a fazer é alterar as frases originais para que elas levem em conta um novo elemento da estrutura da expressão, e pode haver mais propostas a partir disso. Uma vez modificadas adequadamente, a implementação se torna quase formal.