¿Analizador de ecuaciones (expresiones) con precedencia?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He desarrollado un analizador de ecuaciones utilizando un algoritmo de pila simple que manejará operadores binarios (+, -, |, &, *, /, etc.), operadores unarios (!) y paréntesis.
Sin embargo, usar este método me deja con todo con la misma prioridad: se evalúa de izquierda a derecha independientemente del operador, aunque la prioridad se puede imponer mediante paréntesis.
Así que ahora "1+11*5" devuelve 60, no 56 como cabría esperar.
Si bien esto es adecuado para el proyecto actual, quiero tener una rutina de propósito general que pueda usar para proyectos posteriores.
Editado para mayor claridad:
¿Cuál es un buen algoritmo para analizar ecuaciones con precedencia?
Estoy interesado en algo simple de implementar y entender que puedo codificar yo mismo para evitar problemas de licencia con el código disponible.
Gramática:
No entiendo la pregunta de gramática; la escribí a mano.Es tan simple que no veo la necesidad de YACC o Bison.Simplemente necesito calcular cadenas con ecuaciones como "2+3 * (42/13)".
Idioma:
Estoy haciendo esto en C, pero estoy interesado en un algoritmo, no en una solución específica del lenguaje.C tiene un nivel lo suficientemente bajo como para que sea fácil convertirlo a otro idioma si fuera necesario.
Ejemplo de código
publiqué el código de prueba para el analizador de expresiones simples Estaba hablando de arriba.Los requisitos del proyecto cambiaron y, por lo tanto, nunca tuve que optimizar el código para el rendimiento o el espacio, ya que no se incorporó al proyecto.Está en la forma detallada original y debe ser fácilmente comprensible.Si hago algo más en términos de precedencia de operadores, probablemente elegiré el truco de macros porque coincide con el resto del programa en simplicidad.Sin embargo, si alguna vez uso esto en un proyecto real, optaré por un analizador más compacto y rápido.
Pregunta relacionada
-Adán
Solución
El camino difícil
Quieres un analizador de descenso recursivo.
Para obtener prioridad, debe pensar de forma recursiva, por ejemplo, utilizando su cadena de muestra,
1+11*5
Para hacer esto manualmente, tendrías que leer el 1, luego vea el plus y comience una "sesión" de análisis recursivo completamente nueva comenzando con 11...y asegúrese de analizar el 11 * 5 en su propio factor, produciendo un árbol de análisis sintáctico con 1 + (11 * 5).
Todo esto resulta tan doloroso incluso al intentar explicarlo, especialmente con la impotencia añadida de C.Mira, después de analizar el 11, si * fuera en realidad un +, tendrías que abandonar el intento de crear un término y en su lugar analizar el 11 él mismo como un factor.Mi cabeza ya está explotando.Es posible con la estrategia recursiva decente, pero hay una manera mejor...
La manera fácil (correcta)
Si utiliza una herramienta GPL como Bison, probablemente no necesite preocuparse por problemas de licencia, ya que el código C generado por bison no está cubierto por la GPL (IANAL, pero estoy bastante seguro de que las herramientas GPL no fuerzan la GPL). código/binarios generados;por ejemplo, Apple compila código como, por ejemplo, Aperture con GCC y lo venden sin tener que obtener la GPL de dicho código).
Descargar Bisonte (o algo equivalente, ANTLR, etc.).
Por lo general, hay algún código de muestra en el que puede ejecutar bison y obtener el código C deseado que demuestra esta calculadora de cuatro funciones:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Mire el código generado y verá que esto no es tan fácil como parece.Además, las ventajas de usar una herramienta como Bison son 1) aprendes algo (especialmente si lees el libro de Dragon y aprendes sobre gramáticas), 2) evitas NIH tratando de reinventar la rueda.Con una herramienta generadora de analizadores real, en realidad tienes la esperanza de ampliarla más adelante, mostrando a otras personas que sabes que los analizadores son el dominio de las herramientas de análisis.
Actualizar:
La gente aquí ha ofrecido muchos buenos consejos.Mi única advertencia contra saltarse las herramientas de análisis o simplemente usar el algoritmo Shunting Yard o un analizador recursivo decente hecho a mano es que los pequeños lenguajes de juguete1 algún día pueden convertirse en grandes lenguajes reales con funciones (sin, cos, log) y variables, condiciones y bucles for.
Es muy posible que Flex/Bison sea excesivo para un intérprete pequeño y simple, pero un analizador + evaluador único puede causar problemas en el futuro cuando sea necesario realizar cambios o agregar funciones.Su situación variará y necesitará utilizar su criterio;simplemente no lo hagas castigar a otras personas por tus pecados [2] y construir una herramienta poco adecuada.
Mi herramienta favorita para analizar
La mejor herramienta del mundo para el trabajo es la Pársec biblioteca (para analizadores recursivos decentes) que viene con el lenguaje de programación Haskell.Se parece mucho BNF, o como alguna herramienta especializada o lenguaje de dominio específico para análisis (código de muestra [3]), pero en realidad es solo una biblioteca normal en Haskell, lo que significa que se compila en el mismo paso de compilación que el resto de su código Haskell, y puede escribir código Haskell arbitrario y llamarlo dentro de su analizador, y puede mezclar y combinar otras bibliotecas todo en el mismo código.(Por cierto, incorporar un lenguaje de análisis como este en un lenguaje que no sea Haskell da como resultado un montón de problemas sintácticos.Hice esto en C# y funciona bastante bien, pero no es tan bonito ni conciso).
Notas:
1 Richard Stallman dice, en Por qué no deberías usar Tcl
La principal lección de emacs es que un lenguaje para las extensiones no debe ser un mero "lenguaje de extensión".Debe ser un lenguaje de programación real, diseñado para escribir y mantener programas sustanciales.¡Porque la gente querrá hacer eso!
[2] Sí, siempre tendré cicatrices por usar ese "lenguaje".
También tenga en cuenta que cuando envié esta entrada, la vista previa era correcta, pero El analizador poco adecuado de SO se comió mi etiqueta de anclaje cercana en el primer párrafo, lo que demuestra que los analizadores no son algo con lo que se pueda jugar porque si usas expresiones regulares y trucos únicos probablemente te equivoques en algo sutil y pequeño.
[3] Fragmento de un analizador Haskell que utiliza Parsec:una calculadora de cuatro funciones ampliada con exponentes, paréntesis, espacios en blanco para la multiplicación y constantes (como pi y e).
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
Otros consejos
El algoritmo del patio de maniobras es la herramienta adecuada para esto.Wikipedia es realmente confusa al respecto, pero básicamente el algoritmo funciona así:
Digamos que quieres evaluar 1 + 2 * 3 + 4.Intuitivamente, "sabes" que primero tienes que hacer el 2 * 3, pero ¿cómo obtienes este resultado?La clave es darse cuenta de que cuando escanea la cadena de izquierda a derecha, evaluará un operador cuando el operador que sigue tiene una precedencia menor (o igual).En el contexto del ejemplo, esto es lo que desea hacer:
- Mira a:1 + 2, no hagas nada.
- Ahora mira 1 + 2 * 3, todavía no hagas nada.
- Ahora mire 1 + 2 * 3 + 4, ahora sabe que 2 * 3 debe evaluarse porque el siguiente operador tiene menor prioridad.
¿Cómo implementas esto?
Desea tener dos pilas, una para números y otra para operadores.Empujas números en la pila todo el tiempo.Compara cada nuevo operador con el que está en la parte superior de la pila, si el que está en la parte superior de la pila tiene mayor prioridad, lo saca de la pila de operadores, saca los operandos de la pila de números, aplica el operador y envía el resultado. en la pila de números.Ahora repite la comparación con el operador de la parte superior de la pila.
Volviendo al ejemplo, funciona así:
N = [] ops = [
- Leer 1.N = [1], Operaciones = [ ]
- Leer +.N = [1], Operaciones = [+]
- Leer 2.N = [1 2], Operaciones = [+]
- Leer
*.N = [1 2], Operaciones = [+ *] - Leer 3.N = [1 2 3], Operaciones = [+ *]
- Leer +.N = [1 2 3], Operaciones = [+ *]
- Pop 3, 2 y ejecutar 2
*3 y empuja el resultado hacia N.N = [1 6], Operaciones = [+] +queda asociativo a la izquierda, por lo que también desea quitar 1, 6 y ejecutar +.N = [7], Operaciones = [].- Finalmente, empuje el [+] hacia la pila del operador.N = [7], Operaciones = [+].
- Pop 3, 2 y ejecutar 2
- Leer 4.norte = [7 4].Operaciones = [+].
- Se te acabaron las entradas, por lo que deseas vaciar las pilas ahora.Con lo cual obtendrás el resultado 11.
Ahí eso no es tan difícil, ¿verdad?Y no realiza invocaciones a ninguna gramática o generador de analizadores.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Muy buena explicación de diferentes enfoques:
- Reconocimiento de descenso recursivo
- El algoritmo del patio de maniobras
- La solución clásica
- Escalada de precedencia
Escrito en lenguaje sencillo y pseudocódigo.
Me gusta el de 'escalada de precedencia'.
Hay un buen articulo. aquí sobre la combinación de un analizador de descenso recursivo simple con un análisis de precedencia de operadores.Si ha estado escribiendo analizadores recientemente, su lectura debería ser muy interesante e instructiva.
Hace mucho tiempo, inventé mi propio algoritmo de análisis, que no pude encontrar en ningún libro sobre análisis (como el Libro del Dragón).Al observar los indicadores del algoritmo Shunting Yard, veo el parecido.
Hace aproximadamente 2 años, hice una publicación al respecto, completa con el código fuente de Perl, en http://www.perlmonks.org/?node_id=554516.Es fácil portar a otros idiomas:La primera implementación que hice fue en el ensamblador Z80.
Es ideal para cálculos directos con números, pero puedes usarlo para producir un árbol de análisis si es necesario.
Actualizar Debido a que más personas pueden leer (o ejecutar) Javascript, reimplementé mi analizador en Javascript, después de reorganizar el código.Todo el analizador tiene menos de 5k de código Javascript (alrededor de 100 líneas para el analizador, 15 líneas para una función contenedora), incluido el informe de errores y los comentarios.
Puede encontrar una demostración en vivo en http://users.telenet.be/bartl/expressionParser/expressionParser.html.
// operator table
var ops = {
'+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
'-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
'*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
'/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
'**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};
// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };
// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
var startOffset = r.offset;
var value;
var m;
// floating point number
// example of parsing ("lexing") without aid of regular expressions
value = 0;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
if(r.string.substr(r.offset, 1) == ".") {
r.offset++;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
}
if(r.offset > startOffset) { // did that work?
// OK, so I'm lazy...
return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
} else if(r.string.substr(r.offset, 1) == "+") { // unary plus
r.offset++;
return parseVal(r);
} else if(r.string.substr(r.offset, 1) == "-") { // unary minus
r.offset++;
return negate(parseVal(r));
} else if(r.string.substr(r.offset, 1) == "(") { // expression in parens
r.offset++; // eat "("
value = parseExpr(r);
if(r.string.substr(r.offset, 1) == ")") {
r.offset++;
return value;
}
r.error = "Parsing error: ')' expected";
throw 'parseError';
} else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name
// sorry for the regular expression, but I'm too lazy to manually build a varname lexer
var name = m[0]; // matched string
r.offset += name.length;
if(name in vars) return vars[name]; // I know that thing!
r.error = "Semantic error: unknown variable '" + name + "'";
throw 'unknownVar';
} else {
if(r.string.length == r.offset) {
r.error = 'Parsing error at end of string: value expected';
throw 'valueMissing';
} else {
r.error = "Parsing error: unrecognized value";
throw 'valueNotParsed';
}
}
}
function negate (value) {
return -value;
}
function parseOp(r) {
if(r.string.substr(r.offset,2) == '**') {
r.offset += 2;
return ops['**'];
}
if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
return ops[r.string.substr(r.offset++, 1)];
return null;
}
function parseExpr(r) {
var stack = [{precedence: 0, assoc: 'L'}];
var op;
var value = parseVal(r); // first value on the left
for(;;){
op = parseOp(r) || {precedence: 0, assoc: 'L'};
while(op.precedence < stack[stack.length-1].precedence ||
(op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {
// precedence op is too low, calculate with what we've got on the left, first
var tos = stack.pop();
if(!tos.exec) return value; // end reached
// do the calculation ("reduce"), producing a new value
value = tos.exec(tos.value, value);
}
// store on stack and continue parsing ("shift")
stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
value = parseVal(r); // value on the right
}
}
function parse (string) { // wrapper
var r = {string: string, offset: 0};
try {
var value = parseExpr(r);
if(r.offset < r.string.length){
r.error = 'Syntax error: junk found at offset ' + r.offset;
throw 'trailingJunk';
}
return value;
} catch(e) {
alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
return;
}
}
Sería útil si pudiera describir la gramática que está utilizando actualmente para analizar.¡Parece que el problema podría estar ahí!
Editar:
El hecho de que no entiendas la pregunta de gramática y que 'has escrito esto a mano' probablemente explica por qué tienes problemas con expresiones de la forma '1+11*5' (es decir, con precedencia de operadores) .Buscar en Google "gramática para expresiones aritméticas", por ejemplo, debería arrojar algunos buenos consejos.Esta gramática no tiene por qué ser complicada:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
funcionaría, por ejemplo, y se puede aumentar trivialmente para ocuparse de algunas expresiones más complicadas (incluidas funciones, por ejemplo, o potencias,...).
Te sugiero que eches un vistazo este hilo, por ejemplo.
Casi todas las introducciones a la gramática/análisis tratan las expresiones aritméticas como ejemplo.
Tenga en cuenta que utilizar una gramática no implica en absoluto utilizar una herramienta específica (a la Yacc, Bisonte,...).De hecho, seguramente ya estás utilizando la siguiente gramática:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(o algo por el estilo) ¡sin saberlo!
¿Has pensado en usar Impulsar el espíritu?Le permite escribir gramáticas similares a EBNF en C++ de esta manera:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
Al formular su pregunta, no hay necesidad de recursividad alguna.La respuesta es tres cosas:Notación Postfix más algoritmo Shunting Yard más evaluación de expresiones Postfix:
1).Notación Postfix = inventada para eliminar la necesidad de una especificación de precedencia explícita.Lea más en la red, pero aquí está la esencia:La expresión infija ( 1 + 2 ) * 3, si bien es fácil de leer y procesar para los humanos, no es muy eficiente para la computación a través de una máquina.¿Qué es?Regla simple que dice "reescribir la expresión almacenándola en caché con prioridad, luego procesarla siempre de izquierda a derecha".Entonces el infijo ( 1 + 2 ) * 3 se convierte en un sufijo 12+3*.POST porque el operador se coloca siempre DESPUÉS de los operandos.
2).Evaluación de expresiones sufijas.Fácil.Leer números de una cadena postfix.Empújelos sobre una pila hasta que vea a un operador.Verifique el tipo de operador: ¿unario?¿binario?¿terciario?Extraiga tantos operandos de la pila como sea necesario para evaluar este operador.Evaluar.¡Vuelva a colocar el resultado en la pila!Y ya casi terminas.Continúe haciéndolo hasta que la pila tenga solo una entrada = valor que está buscando.
Hagamos ( 1 + 2 ) * 3 que está en sufijo es "12+3*".Leer el primer número = 1.Empújelo sobre la pila.Lea a continuación.Número = 2.Empújelo sobre la pila.Lea a continuación.Operador.¿Cuál?+.¿Que tipo?Binario = necesita dos operandos.Haga estallar la pila dos veces = argright es 2 y argleft es 1.1 + 2 es 3.Empuje 3 hacia atrás en la pila.Lea a continuación de la cadena postfix.Es un número.3.Empujar.Lea a continuación.Operador.¿Cuál?*.¿Que tipo?Binario = necesita dos números -> pop stack dos veces.Primero ingrese a argright, segunda vez a argleft.Evaluar la operación: 3 por 3 es 9. Empuje 9 en la pila.Lea el siguiente carácter postfijo.Es nulo.Fin de la entrada.Pop stack onec = esa es tu respuesta.
3).Shunting Yard se utiliza para transformar una expresión infija (fácilmente) legible por humanos en una expresión postfija (también fácilmente legible por humanos después de un poco de práctica).Fácil de codificar manualmente.Ver comentarios arriba y netos.
Depende de qué tan "general" quieras que sea.
Si desea que sea realmente general, como poder analizar funciones matemáticas y también como sin(4+5)*cos(7^3), probablemente necesitará un árbol de análisis.
En lo cual, no creo que sea apropiado pegar aquí una implementación completa.Te sugiero que eches un vistazo a uno de los infames "libro del dragón".
Pero si solo quieres soporte de prioridad, entonces podrías hacerlo convirtiendo primero la expresión a forma de sufijo en la que debería estar disponible un algoritmo que puedas copiar y pegar Google o creo que puedes codificarlo tú mismo con un árbol binario.
Cuando lo tienes en forma de postfijo, a partir de ese momento es pan comido, ya que ya entiendes cómo ayuda la pila.
Yo sugeriría hacer trampa y usar el Algoritmo de patio de maniobras.Es una forma sencilla de escribir un analizador simple tipo calculadora y tiene en cuenta la prioridad.
Si desea tokenizar adecuadamente las cosas y tener variables, etc.involucrado, entonces seguiría adelante y escribiría un analizador de descenso recursivo como lo sugieren otros aquí; sin embargo, si simplemente necesita un analizador estilo calculadora, entonces este algoritmo debería ser suficiente :-)
Encontré esto en la lista PIC sobre el Algoritmo del patio de maniobras:
Harold escribe:
Recuerdo haber leído hace mucho tiempo, de un algoritmo que convirtió las expresiones algebraicas en RPN para una fácil evaluación.Cada valor infijo u operador o paréntesis fue representado por un automóvil ferroviario en una vía.Un tipo de automóvil se separó en otra pista y el otro continuó en línea recta.No recuerdo los detalles (¡obviamente!), Pero siempre pensé que sería interesante codificar.Esto es de regreso cuando estaba escribiendo el código de ensamblaje 6800 (no 68000).
Este es el "algorythm de patio de derivación" y es lo que usan la mayoría de los analizadores de la máquina.Vea el artículo sobre análisis en Wikipedia.Una manera fácil de codificar el algorythm de la patio de derivación es usar dos pilas.Uno es la pila de "empuje" y la otra la pila de "reducir" o "resultado".Ejemplo:
pstack = () // Entrada de rstack = () vacía:1+2*3 Precedencia = 10 // Reducción más baja = 0 // No reduzca
comenzar:ficha '1':isnumber, poner en pstack (push) token '+':isoperator establece precedencia = 2 si precedencia <anterior_operator_precedence luego reduzca () // ver a continuación poner '+' en pstack (push) token '2':isnumber, puso en pstack (push) token '*':isoperator, establecer precedencia = 1, poner en pstack (push) // verifique la precedencia como // arriba token '3':ISNumber, Put en el extremo de la entrada Pstack (Push), necesita reducir (el objetivo es vacío pstack) reducir () // hecho
Para reducir, los elementos POP de la pila de empuje y colocarlos en la pila de resultados, siempre intercambie los 2 elementos superiores en pstack si son del formulario 'operador' 'número':
pila de datos:'1' '+' '2' '' '3' pila:() ...pila de datos:() pila:'3' '2' '' '1' '+'
si la expresión hubiera sido:
1*2+3
Entonces, el disparador de reducción habría sido la lectura del token '+' que tiene un precio más bajo que el '*' ya empujado, por lo que lo habría hecho:
pila de datos:'1' '' '2' pila:()...pila de datos:() pila:'1' '2' ''
y luego empujó '+' y luego '3' y finalmente se redujo:
pila de datos:'+' '3' pila:'1' '2' ''...pila de datos:() pila:'1' '2' '' '3' '+'
Entonces la versión corta es:Empuje los números, al presionar a los operadores, verifique la precedencia del operador anterior.Si fue más alto que el de los operadores que se debe empujar ahora, primero reduzca, luego presione el operador actual.Para manejar los parens, simplemente guarde la precedencia del operador 'anterior' y coloque una marca en el pstack que le indique el algorio de reducir que deje de reducir al resolver el interior de un par de paren.El paren de cierre desencadena una reducción al igual que el final de la entrada, y también elimina la marca de paren abierto del pstack, y restaura la precedencia de 'operación anterior' para que el análisis pueda continuar después del paren cerrado donde lo dejó.Esto se puede hacer con recursión o sin (pista:Use una pila para almacenar la precedencia anterior al encontrar un '(' ...).La versión generalizada de esto es utilizar un generador de analizador implementado algorythm, F.Ex.Usando YACC o bisonte o taccle (análogo de TCL de YACC).
Pedro
-Adán
He publicado la fuente de un ultracompacto (1 clase, <10 KiB) Evaluador de matemáticas de Java en mi sitio web.Este es un analizador de descenso recursivo del tipo que causó la explosión craneal del cartel de la respuesta aceptada.
Admite precedencia completa, paréntesis, variables con nombre y funciones de un solo argumento.
Lancé un analizador de expresiones basado en Patio de maniobras de Dijkstra algoritmo, bajo los términos del Licencia Apache 2.0:
Otro recurso para el análisis de precedencia es el Analizador de precedencia de operadores entrada en Wikipedia.Cubre el algoritmo del patio de maniobras de Dijkstra y un algoritmo alternativo de árbol, pero más notablemente cubre un algoritmo de reemplazo de macros realmente simple que puede implementarse trivialmente frente a cualquier analizador ignorante de precedencia:
#include <stdio.h>
int main(int argc, char *argv[]){
printf("((((");
for(int i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(argv[i]){
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+': printf(")))+((("); continue;
case '-': printf(")))-((("); continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
Invocarlo como:
$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
Lo cual es asombroso por su simplicidad y muy comprensible.
He implementado un analizador de descenso recursivo en Java en el Analizador MathEclipse proyecto.También podría usarse como Kit de herramientas web de Google módulo
Actualmente estoy trabajando en una serie de artículos sobre la creación de un analizador de expresiones regulares como herramienta de aprendizaje para patrones de diseño y programación legible.Puedes echar un vistazo a código legible.El artículo presenta un uso claro del algoritmo de los patios de maniobras.
Escribí un analizador de expresiones en F# y blogueó sobre esto aquí.Utiliza el algoritmo del patio de maniobras, pero en lugar de convertir de infijo a RPN, agregué una segunda pila para acumular los resultados de los cálculos.Maneja correctamente la precedencia de operadores, pero no admite operadores unarios.Escribí esto para aprender F#, no para aprender a analizar expresiones.
Se puede encontrar una solución Python que usa pyparsing aquí.Analizar la notación infija con varios operadores con precedencia es bastante común, por lo que pyparsing también incluye la infixNotation (antes operatorPrecedence) generador de expresiones.Con él puedes definir fácilmente expresiones booleanas usando "Y", "O", "NO", por ejemplo.O puede ampliar su aritmética de cuatro funciones para utilizar otros operadores, como !para factorial, o '%' para módulo, o agregue operadores P y C para calcular permutaciones y combinaciones.Podría escribir un analizador infijo para notación matricial, que incluya el manejo de operadores '-1' o 'T' (para inversión y transposición).El ejemplo de operatorPrecedence de un analizador de 4 funciones (con '!' agregado por diversión) es aquí y un analizador y evaluador con más funciones es aquí.
Sé que esta es una respuesta tardía, pero acabo de escribir un pequeño analizador que permite que todos los operadores (prefijo, postfijo e infijo izquierdo, infijo derecho y no asociativo) tengan precedencia arbitraria.
Voy a ampliar esto para un lenguaje con soporte DSL arbitrario, pero solo quería señalar que no se necesitan analizadores personalizados para la precedencia de operadores, se puede usar un analizador generalizado que no necesita tablas en absoluto y simplemente busca la precedencia de cada operador tal como aparece.La gente ha estado mencionando analizadores Pratt personalizados o analizadores de patio de maniobras que pueden aceptar entradas ilegales; este no necesita ser personalizado y (a menos que haya un error) no aceptará entradas incorrectas.No está completo en cierto sentido, fue escrito para probar el algoritmo y su entrada está en un formato que necesitará algún preprocesamiento, pero hay comentarios que lo dejan claro.
Tenga en cuenta que faltan algunos tipos comunes de operadores, por ejemplo, el tipo de operador utilizado para indexar la tabla de IE [índice] o llamar a una función de función (parámetro-expresión, ...) Voy a agregarlos, pero piense en ambos como postfix Los operadores donde lo que se interpone entre los delimeters '[' y ']' o '(' y ')' se analiza con una instancia diferente del analizador de expresión.Lamento haber omitido eso, pero la parte del sufijo está incluida; agregar el resto probablemente casi duplicará el tamaño del código.
Dado que el analizador tiene solo 100 líneas de código de raqueta, tal vez debería pegarlo aquí, espero que no sea más largo de lo que permite stackoverflow.
Algunos detalles sobre decisiones arbitrarias:
Si un operador de prefijo de baja precedencia compite por los mismos bloques de infijo que un operador de prefijo de baja precedencia, el operador de prefijo gana.Esto no aparece en la mayoría de los idiomas ya que la mayoría no tiene operadores postfix de baja precedencia.- por ejemplo:((datos a) (izquierda 1 +) (pre 2 no) (datos b) (post 3!) (izquierda 1 +) (datos c)) es A +no b! +c donde no es un operador de prefijo y!es operador postfix y ambos tienen una precedencia menor que+, por lo que quieren agruparse de manera incompatible, ya sea (a+no b!)+c o como a+(no b!+c) en estos casos, el operador de prefijo siempre gana, por lo que el el segundo es la forma en que analiza
Los operadores infijos no asociativos realmente existen para que no tenga que fingir que los operadores que devuelven tipos diferentes de los que toman tienen sentido juntos, pero sin tener diferentes tipos de expresión para cada uno es una chapuza.Como tal, en este algoritmo, los operadores no asociativos se niegan a asociarse no sólo consigo mismos sino con cualquier operador con la misma precedencia.Ese es un caso común ya que < <= == >= etc. no se asocian entre sí en la mayoría de los idiomas.
La cuestión de cómo diferentes tipos de operadores (izquierda, prefijo, etc.) rompen los lazos de precedencia no debería surgir, porque en realidad no tiene sentido dar a operadores de diferentes tipos la misma precedencia.Este algoritmo hace algo en esos casos, pero ni siquiera me molesto en averiguar exactamente qué porque, en primer lugar, esa gramática es una mala idea.
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value '())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type 'post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type 'post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type 'left) (handle-infix process-prec 0))
((eq? input-type 'right) (handle-infix process-prec 1))
((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type 'pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type 'data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type 'grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)
Aquí hay una solución recursiva de caso simple escrita en Java.Tenga en cuenta que no maneja números negativos, pero puede agregarlos si lo desea:
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == '(') bracketCounter++;
else if(c == ')') bracketCounter--;
else if((c == '+' || c == '-') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case '+':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case '-':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case '*':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case '/':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}
El algoritmo podría codificarse fácilmente en C como analizador de descenso recursivo.
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - '0');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != '+')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);
return 0;
}
Las siguientes bibliotecas pueden ser útiles: yupana - operaciones estrictamente aritméticas; pequeñaexpr - operaciones aritméticas + funciones matemáticas en C + una proporcionada por el usuario; mpc - combinadores de analizadores
Explicación
Capturemos una secuencia de símbolos que representan una expresión algebraica.El primero es un número, es decir, un dígito decimal repetido una o más veces.Nos referiremos a dicha notación como regla de producción.
number -> [0..9]+
El operador de suma con sus operandos es otra regla.es cualquiera number o cualquier símbolo que represente sum "*" sum secuencia.
sum -> number | sum "+" sum
Pruebe el sustituto number en sum "+" sum eso será number "+" number que a su vez podría ampliarse a [0..9]+ "+" [0..9]+ que finalmente podría reducirse a 1+8 que es la expresión de suma correcta.
Otras sustituciones también producirán una expresión correcta: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
Poco a poco podríamos parecer un conjunto de reglas de producción. también conocido como gramática que expresan todas las expresiones algebraicas posibles.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
Para controlar la precedencia del operador, altere la posición de su regla de producción frente a otras.Mire la gramática anterior y observe que la regla de producción para * se coloca debajo + esto obligará product evaluar antes sum.La implementación simplemente combina el reconocimiento de patrones con la evaluación y, por lo tanto, refleja fielmente las reglas de producción.
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
Aquí evaluamos term primero y devuélvelo si no hay * personaje después de él Esta es la elección que queda en nuestra regla de producción. de lo contrario, evalúe los símbolos después y regrese term.value * product.value Esta es la elección correcta en nuestra regla de producción, es decir. term "*" product
