Analizador de ecuaciones (expresión) con precedencia?

Desarrollé un analizador de ecuaciones usando 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 lo que tiene la misma precedencia: se evalúa de izquierda a derecha independientemente del operador, aunque la precedencia se puede aplicar usando paréntesis.

Así que ahora mismo "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 entiendo que puedo codificarme para evitar problemas de licencia con el código disponible.

Gramática:

No entiendo la pregunta de gramática, lo he escrito 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 es lo suficientemente bajo como para que sea fácil convertirlo a otro idioma en caso de que sea necesario.

Ejemplo de código

Publiqué el código de prueba para el analizador de expresiones simples del que estaba hablando anteriormente. Los requisitos del proyecto se modificaron y, por lo tanto, nunca tuve que optimizar el código para el rendimiento o el espacio, ya que no estaba incorporado al proyecto. Está en su forma detallada original y debe ser fácilmente comprensible. Si hago algo más con él 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 utilizo esto en un proyecto real, buscaré un analizador más compacto / rápido.

Pregunta relacionada

¿Diseño inteligente de un analizador matemático?

-Adán

El camino difícil

Quieres un analizador de descenso recursivo .

Para obtener precedencia, debe pensar de forma recursiva, por ejemplo, utilizando su cadena de muestra,

1+11*5

para hacer esto manualmente, tendría que leer el 1 , luego ver el más y comenzar una nueva "sesión" de análisis recursivo comenzando con 11... y asegurarse de analizar el 11 * 5en su propio factor, produciendo un árbol de análisis con 1 + (11 * 5).

Todo esto se siente tan doloroso incluso para intentar explicarlo, especialmente con la impotencia adicional de C. Ver, después de analizar el 11, si el * fuera realmente un + en su lugar, tendría que abandonar el intento de hacer un término y en su lugar analizar el 11sí mismo como un factor. Mi cabeza ya esta explotando. Es posible con la estrategia recursiva decente, pero hay una mejor manera ...

La forma fácil (correcta)

Si usa 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 en código generado / binarios; por ejemplo, Apple compila código como, por ejemplo, Aperture con GCC y lo venden sin tener que GPL dicho código).

Descarga Bison (o algo equivalente, ANTLR, etc.).

Por lo general, hay un 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 vea 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 Dragon y aprendes sobre las gramáticas), 2) evitas que los NIH intenten reinventar la rueda. Con una herramienta generadora de analizadores sintácticos real, en realidad tiene la esperanza de escalar más adelante, mostrando a otras personas que sabe que los analizadores son el dominio de las herramientas de análisis sintáctico.

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 decente recursivo enrollado a mano es que los pequeños lenguajes de juguete ¹ pueden convertirse algún día en grandes lenguajes reales con funciones (sin, cos, log) y variables, condiciones y para bucles.

Flex / Bison puede ser excesivo para un intérprete pequeño y simple, pero un analizador + evaluador único puede causar problemas en el futuro cuando es necesario realizar cambios o agregar funciones. Su situación variará y deberá utilizar su criterio; simplemente no castigue a otras personas por sus pecados ^[2] y construya una herramienta menos que adecuada.

Mi herramienta favorita para analizar

La mejor herramienta del mundo para el trabajo es la biblioteca Parsec (para analizadores decentes recursivos) que viene con el lenguaje de programación Haskell. Se parece mucho a BNF , oa alguna herramienta especializada o lenguaje específico de dominio para analizar (código de muestra [3]), pero de hecho es solo una biblioteca normal en Haskell, lo que significa que 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 en el mismo código . (Por cierto, incrustar un lenguaje de análisis como este en un lenguaje que no sea Haskell da como resultado un montón de cruft sintáctico. Hice esto en C # y funciona bastante bien, pero no es tan bonito y sucinto).

Notas:

1 Richard Stallman dice, en Por qué no debería usar Tcl

La principal lección de Emacs es que un lenguaje para 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 importantes. ¡Porque la gente querrá hacer eso!

[2] Sí, siempre estoy asustado por usar ese "lenguaje".

También tenga en cuenta que cuando presenté esta entrada, la vista previa era correcto, pero SO de menos de analizador adecuada comió mi estrecha etiqueta de anclaje en el primer párrafo , lo que demuestra que los analizadores no son algo que se podía jugar porque si utiliza expresiones regulares y uno de los cortes que probablemente obtendrá algo sutil y pequeño mal .

[3] Fragmento de un analizador de Haskell que usa Parsec: una calculadora de cuatro funciones extendida con exponentes, paréntesis, espacios en blanco para multiplicar 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

El algoritmo del patio de maniobras es la herramienta adecuada para esto. Wikipedia es realmente confuso sobre esto, pero básicamente el algoritmo funciona así:

Digamos que quieres evaluar 1 + 2 * 3 + 4. Intuitivamente, "sabes" que tienes que hacer el 2 * 3 primero, pero ¿cómo obtienes este resultado? La clave es darse cuenta de que cuando está escaneando la cadena de izquierda a derecha, evaluará a un operador cuando el operador que lo sigue tenga una precedencia menor (o igual a). En el contexto del ejemplo, esto es lo que quiere hacer:

1. Mira: 1 + 2, no hagas nada.
2. Ahora mire 1 + 2 * 3, todavía no haga nada.
3. Ahora mire 1 + 2 * 3 + 4, ahora sabe que 2 * 3 debe evaluarse porque el siguiente operador tiene menor precedencia.

¿Cómo implementas esto?

Quieres tener dos pilas, una para números y otra para operadores. Empujas números en la pila todo el tiempo. Usted compara cada operador nuevo 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 empuja 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 = [] Operaciones = []

• 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 ejecute 2 *3, y presione el resultado en N. N = [1 6], Ops = [+]
  • +es asociativo a la izquierda, por lo que también desea extraer 1, 6 y ejecutar +. N = [7], Operaciones = [].
  • Finalmente, empuje el [+] sobre la pila del operador. N = [7], Operaciones = [+].
• Leer 4. N = [7 4]. Ops = [+].
• Se ha quedado sin entrada, por lo que quiere vaciar las pilas ahora. Sobre lo cual obtendrás el resultado 11.

Ahí, eso no es tan difícil, ¿verdad? Y no hace invocaciones a ninguna gramática o generador de analizadores sintácticos.

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 uno de 'escalada de precedencia'.

Hay un buen artículo aquí en la combinación de un simple analizador sintáctico descendente recursivo con el análisis sintáctico por precedencia de operadores. Si ha estado escribiendo analizadores sintácticos recientemente, debería ser muy interesante e instructivo de leer.

Hace mucho tiempo, inventé mi propio algoritmo de análisis, que no pude encontrar en ningún libro sobre análisis (como el Dragon Book). Mirando los indicadores del algoritmo Shunting Yard, veo el parecido.

Hace unos 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 de migrar a otros lenguajes: la primera implementación que hice fue en el ensamblador Z80.

Es ideal para el cálculo directo con números, pero puede usarlo para producir un árbol de análisis si es necesario.

Actualizar Debido a que más personas pueden leer (o ejecutar) Javascript, he vuelto a implementar mi analizador en Javascript, después de que el código se haya reorganizado. El analizador completo tiene menos de 5k de código Javascript (alrededor de 100 líneas para el analizador, 15 líneas para una función contenedora), incluidos informes de errores y 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 comprenda la pregunta gramatical y de que 'haya escrito esto a mano' probablemente explique por qué tiene 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 encargarse de algunas expresiones más complicadas (incluidas funciones, por ejemplo, o poderes, ...).

Te sugiero que eches un vistazo a esto hilo, por ejemplo.

Casi todas las introducciones a las gramáticas / análisis sintáctico tratan las expresiones aritméticas como ejemplo.

Tenga en cuenta que usar una gramática no implica en absoluto usar una herramienta específica ( a la Yacc, Bison, ...). De hecho, seguramente ya está usando la siguiente gramática:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(o algo por el estilo) sin saberlo!

¿Has pensado en utilizar Boost Spirit ? Le permite escribir gramáticas similares a EBNF en C ++ así:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));

Al formular su pregunta, no hay necesidad de recursividad en absoluto. La respuesta es tres cosas: notación Postfix más algoritmo Shunting Yard más evaluación de expresión Postfix:

1). Notación de sufijo = inventado para eliminar la necesidad de una especificación de precedencia explícita. Lea más en la red, pero aquí está la esencia: expresión infija (1 + 2) * 3, aunque fácil de leer y procesar para los humanos, no es muy eficiente para la computación a través de una máquina. ¿Que es? Regla simple que dice "reescribir la expresión almacenando en caché en precedencia, luego siempre procesarla de izquierda a derecha". Entonces 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 la expresión de sufijo. Fácil. Lea los números de la cadena de sufijo. Empújelos sobre una pila hasta que vea un operador. Compruebe 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 has terminado. Siga 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 en la pila. Leer a continuación. Número = 2. Empújelo en la pila. Leer a continuación. Operador. ¿Cúal? +. ¿Que tipo? Binario = necesita dos operandos. Pop stack dos veces = argright es 2 y argleft es 1. 1 + 2 es 3. Empuja 3 hacia atrás en la pila. Lea a continuación de la cadena de sufijo. Es un número. 3. Empuje. Leer a continuación. Operador. ¿Cúal? *. ¿Que tipo? Binario = necesita dos números -> pop stack dos veces. Primero aparece en argright, segunda vez en argright. Evalúe la operación: 3 por 3 es 9, presione 9 en la pila. Leer siguiente postfix char. Es nulo. Fin de 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 legible por humanos después de un poco de práctica). Fácil de codificar manualmente. Vea los comentarios arriba y net.

¿Hay algún idioma que quieras usar? ANTLR le permitirá hacer esto desde una perspectiva de Java. Adrian Kuhn tiene un excelente artículo sobre cómo escribir una gramática ejecutable en Ruby; de hecho, su ejemplo es casi exactamente su ejemplo de expresión aritmética.

Depende de qué tan "general" quieras que sea.

Si desea que sea realmente muy general, como poder analizar funciones matemáticas así como sin (4 + 5) * cos (7 ^ 3), probablemente necesitará un árbol de análisis sintáctico.

En lo cual, no creo que una implementación completa sea adecuada para pegar aquí. Te sugiero que consultes uno de los infames " Libro del dragón ".

Pero si solo desea soporte de precedencia , entonces podría hacerlo convirtiendo primero la expresión a la forma de sufijo en la que un algoritmo que puede copiar y pegar debería estar disponible en Google o creo que puede codificarlo usted mismo con un binario árbol.

Cuando lo tiene en forma de postfijo, entonces es pan comido a partir de ese momento, ya que ya comprende cómo ayuda la pila.

Sugeriría hacer trampa y usar el algoritmo Shunting Yard . Es un medio sencillo de escribir un analizador sintáctico simple tipo calculadora y tiene prioridad.

Si desea tokenizar correctamente las cosas y tener variables, etc. involucradas, entonces seguiría adelante y escribiría un analizador de descenso recursivo como lo sugirieron otros aquí, sin embargo, si simplemente necesita un analizador de estilo de calculadora, este algoritmo debería ser suficiente :-)

Encontré esto en la lista PIC sobre el algoritmo Shunting Yard :

Harold escribe:

Recuerdo haber leído, hace mucho tiempo, un algoritmo que convertía expresiones algebraicas a RPN para una fácil evaluación. Cada valor de infijo u operador o paréntesis estaba representado por un vagón de ferrocarril en una vía. Un tipo de coche se dividió en otra pista y el otro siguió recto. No recuerdo los detalles (¡obviamente!), Pero siempre pensé que sería interesante codificar. Esto es cuando estaba escribiendo el código ensamblador 6800 (no 68000).

Este es el "algoritmo del patio de maniobras" y es lo que utilizan la mayoría de los analizadores de máquinas. Consulte el artículo sobre análisis en Wikipedia. Una forma fácil de codificar el algoritmo del patio de maniobras es usar dos pilas. Una es la pila de "empujar" y la otra la pila de "reducir" o "resultado". Ejemplo:

pstack = () // rstack = () vacío input: 1 + 2 * 3 precedence = 10 // menor reducir = 0 // no reducir

start: token '1': isnumber, poner en pstack (push) token '+': isoperator establecer precedence = 2 si precedence <previous_operator_precedence then reduce () // ver más abajo poner '+' en pstack (push) token '2' : isnumber, poner en pstack (push) token '*': isoperator, set precedence = 1, poner en pstack (push) // verificar la precedencia como // arriba del token '3': isnumber, poner en pstack (push) end of entrada, necesidad de reducir (el objetivo es pstack vacío) reduce () // hecho

para reducir, saque elementos de la pila de empuje y colóquelos en la pila de resultados, siempre intercambie los 2 elementos superiores en pstack si tienen el formato 'operador' 'número':

pstack: '1' '+' '2' ' ' '3' rstack: () ... pstack: () rstack: '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 una precedencia menor que el '*' ya pulsado, por lo que habría hecho:

pstack: '1' ' ' '2' rstack: () ... pstack: () rstack: '1' '2' ' '

y luego presionó '+' y luego '3' y finalmente redujo:

pstack: '+' '3' rstack: '1' '2' ' ' ... pstack: () rstack: '1' '2' ' ' '3' '+'

Entonces, la versión corta es: números push, cuando presionan operadores verifican la precedencia del operador anterior. Si era más alto que el del operador que se va a empujar ahora, primero reduzca y luego empuje al operador actual. Para manejar los parientes, simplemente guarde la precedencia del operador 'anterior' y ponga una marca en el pstack que le indique al algoritmo de reducción que deje de reducir al resolver el interior de un par de pares. El par de cierre desencadena una reducción al igual que el final de la entrada, y también elimina la marca de par de par abierto del pstack, y restaura la precedencia de la 'operación anterior' para que el análisis pueda continuar después del par de cierre donde lo dejó. Esto se puede hacer con recursividad o sin (pista: use una pila para almacenar la precedencia anterior cuando encuentre un '(' ...). La versión generalizada de esto es utilizar un generador de analizador sintáctico implementado algoritmo de patio de maniobras, p. Ej. usando yacc o bison o taccle (tcl análogo de yacc).

Pedro

-Adán

Otro recurso para el análisis de precedencia es la entrada del analizador de precedencia del operador 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 en su simplicidad y muy comprensible.

He publicado la fuente de un evaluador de matemáticas Java ultra compacto (1 clase, <10 KiB) en mi sitio web. Este es un analizador sintáctico descendente recursivo del tipo que provocó 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 el algoritmo Shunting Yard de Dijkstra , bajo los términos de la Licencia Apache 2.0 :

http://projects.congrace.de/exp4j/index.html

Implementé un analizador de descenso recursivo en Java en el proyecto MathEclipse Parser . También se puede utilizar como módulo de Google Web Toolkit

Actualmente estoy trabajando en una serie de artículos sobre la construcción de un analizador de expresiones regulares como herramienta de aprendizaje para patrones de diseño y programación legible. Puede echar un vistazo a legiblecode . El artículo presenta un uso claro del algoritmo de patios de maniobras.

Escribí un analizador de expresiones en F # y escribí en un blog sobre él 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. Sin embargo, escribí esto para aprender F #, no para aprender a analizar expresiones.

Una solución de Python usando pyparsing se puede encontrar aquí . Analizar la notación infija con varios operadores con precedencia es bastante común, por lo que pyparsing también incluye el infixNotation(anteriormente operatorPrecedence) generador de expresiones. Con él puede definir fácilmente expresiones booleanas usando "Y", "O", "NO", por ejemplo. O puede expandir su aritmética de cuatro funciones para usar otros operadores, como! para factorial, o '%' para módulo, o agregue operadores P y C para calcular permutaciones y combinaciones. Puede escribir un analizador infijo para la notación matricial, que incluye el manejo de los operadores '-1' o 'T' (para inversión y transposición). El ejemplo de operatorPrecedence de un analizador de 4 funciones (con '!' Incluido para divertirse) está aquí.

Sé que esta es una respuesta tardía, pero acabo de escribir un analizador diminuto que permite que todos los operadores (prefijo, sufijo e infijo izquierdo, infijo derecho y no asociativo) tengan precedencia arbitraria.

Voy a expandir esto para un lenguaje con soporte DSL arbitrario, pero solo quería señalar que uno no necesita analizadores personalizados para la precedencia del operador, uno 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 mencionado analizadores Pratt personalizados o analizadores de patio de maniobras que pueden aceptar entradas ilegales; éste 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 una forma que necesitará algún preprocesamiento, pero hay comentarios que lo aclaran.

Tenga en cuenta que faltan algunos tipos comunes de operadores, por ejemplo, el tipo de operador utilizado para indexar, es decir, tabla [índice] o llamar a una función de función (parámetro-expresión, ...) Voy a agregar esos, pero piense en ambos como sufijo operadores donde lo que se encuentra entre los delimitadores '[' y ']' o '(' y ')' se analiza con una instancia diferente del analizador de expresiones. Lamento haber omitido eso, pero la parte de 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 sufijo de precedencia baja compite por los mismos bloques infijos que un operador de prefijo de precedencia baja, el operador de prefijo gana. Esto no aparece en la mayoría de los lenguajes ya que la mayoría no tiene operadores de sufijo de baja precedencia. - por ejemplo: ((data a) (left 1 +) (pre 2 not) (data b) (post 3!) (left 1 +) (data c)) is a + not b! + c donde not es a operador de prefijo y! es un operador de sufijo y ambos tienen menor precedencia que +, por lo que quieren agrupar de formas incompatibles como (a + no b!) + co como a + (no b! + c) en estos casos el operador de prefijo siempre gana, por lo que el segundo es la forma en que analiza

Los operadores infijos no asociativos están realmente ahí 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 tontería. Como tal, en este algoritmo, los operadores no asociativos se niegan a asociarse no solo con ellos 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 los diferentes tipos de operadores (izquierda, prefijo, etc.) rompen los lazos en la precedencia es una que no debería surgir, porque realmente no tiene sentido dar a los operadores de diferentes tipos la misma precedencia. Este algoritmo hace algo en esos casos, pero ni siquiera me estoy molestando en averiguar exactamente qué, porque esa gramática es una mala idea en primer lugar.

#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 agregar eso 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 se podría codificar fácilmente en C como analizador sintáctico 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 librerías pueden ser útiles: yupana - operaciones estrictamente aritméticas; tinyexpr - operaciones aritméticas + funciones matemáticas C + una proporcionada por el usuario; mpc - combinadores de analizador}

Explicación

Capturemos la secuencia de símbolos que representan la expresión algebraica. El primero es un número, que es 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 uno numbero cualquier símbolo que representa la sum "*" sumsecuencia.

sum -> number | sum "+" sum

Intente sustituir numberen sum "+" sumque será lo number "+" numberque a su vez podría expandirse en lo [0..9]+ "+" [0..9]+que finalmente podría reducirse a 1+8cuál es la expresión de adición correcta.

Otras sustituciones también producirán la expresión correcta: sum "+" sum-> number "+" sum-> number "+" sum "+" sum-> number "+" sum "+" number-> number "+" number "+" number->12+3+5

Poco a poco podríamos parecernos un conjunto de reglas de producción, _{también conocidas 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 otros. Mire la gramática anterior y observe que la regla de producción para *se coloca debajo, +esto obligará a productevaluar 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 termprimero y lo devolvemos si no hay ningún *carácter después, _{esto se deja en nuestra regla de producción; de lo} contrario, evaluamos los símbolos después y devolvemos term.value * product.value _{esta es la elección correcta en nuestra regla de producción, es decir.term "*" product}