Ecuación (expresión) analizador con precedencia?

El algoritmo shunting yard es la herramienta correcta para esto. Wikipedia es muy confusa sobre esto, pero básicamente el algoritmo funciona así:

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

1. Mira: 1 + 2, no hagas nada.
2. Ahora mira 1 + 2 * 3, todavía no hacer nada.
3. Ahora mira 1 + 2 * 3 + 4, ahora sabes que 2 * 3 tiene que ser evaluado porque el siguiente operador tiene menor precedencia.

¿Cómo implementar esto?

Desea tener dos pilas, una para los números y otra para los operadores. Empujas números a la pila todo el tiempo. Usted 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 sacas de la pila de operadores, sacas los operandos de la pila de números, aplicas el operador y empujas el resultado a la pila de números. Ahora repite la comparación con el operador superior de la pila.

Volviendo al ejemplo, funciona así:

N = [ ] Ops = []

• Debe decir 1. N = [1], Ops = []
• Leer +. N = [1], Ops =[+]
• Léase 2. N = [1 2], Ops = [ + ]
• Léase *. N = [12], Ops = [ + *]
• Léase 3. N = [1 2 3], Ops = [ + *]
• Leer +. N = [1 2 3], Ops = [+ *]
  • Pop 3, 2 y ejecutar 2 * 3, y empujar el resultado a N. N =[16], Ops =[+]
  • + se deja asociativo, por lo que desea pop 1, 6 apagado también y ejecutar el +. N = [7], Ops = [].
  • Finalmente empuje el [ + ] en la pila de operadores. N = [7], Ops = [+].
• Léase 4. N = [7 4]. Ops = [+].
• Se ha agotado la entrada, por lo que desea vaciar las pilas ahora. Sobre el que obtendrá el resultado 11.

Ahí, eso no es tan difícil, ¿verdad? Y no hace invocaciones a gramáticas o generadores de analizadores.

Http://www.engr.mun.ca / ~theo/Misc/exp_parsing.htm

Muy buena explicación de los diferentes enfoques:

• Reconocimiento de descenso recursivo
• El algoritmo de la yarda de derivación
• La solución clásica
• Escalada de precedencia

Escrito en lenguaje simple y pseudo-código.

Me gusta la de 'escalada de precedencia'.

Hay un buen artículo aquí sobre la combinación de un analizador de descenso recursivo simple con el análisis de precedencia del operador. Si ha estado escribiendo analizadores 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 Libro del Dragón). Mirando los indicadores del algoritmo del patio de maniobras, veo el parecido.

Hace unos 2 años, hice un post al respecto, completo con el código fuente de Perl, en http://www.perlmonks.org/?node_id=554516 . Es fácil portar 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 se puede utilizar para producir un árbol de análisis si es necesario.

Update Debido a que más personas pueden leer (o ejecutar) Javascript, he reimplementado mi analizador en Javascript, después de que el código se ha reorganizado. Todo el analizador está bajo 5k de código Javascript (alrededor de 100 líneas para el analizador, 15 líneas para una función de envoltura) incluyendo 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 está ahí!

Editar:

El hecho de que no entiendas la pregunta gramatical y que 'has escrito esto a mano' probablemente explica por qué estás teniendo problemas con las expresiones de la forma '1+11*5' (es decir, con precedencia de operador). Buscar en Google 'gramática para expresiones aritméticas', por ejemplo, debería dar algunos buenos punteros. Tal gramática no necesita ser complicado:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

Haría el truco, por ejemplo, y se puede aumentar trivialmente para cuidar de algunas expresiones más complicadas(incluyendo funciones, por ejemplo, o poderes,...).

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

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

Tenga en cuenta que el uso de una gramática no implica en absoluto el uso de una herramienta específica (a la Yacc, Bisonte,...). Efectivamente, ciertamente 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 usar Boost Spirit? Te permite escribir gramáticas similares a EBNF en C++ de la siguiente manera:

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

Al plantear su pregunta no hay necesidad de recursividad alguna. La respuesta es tres cosas: Notación postfijo más algoritmo de Yarda de derivación más evaluación de expresión postfijo:

1). Notación postfijo = inventado para eliminar la necesidad de especificación de precedencia explícita. Leer más en la red, pero aquí está la esencia de la misma: infix expression (1 + 2) * 3 mientras que es fácil para los seres humanos de leer y procesar no es muy eficiente para la computación a través de la máquina. ¿Qué es? Regla simple que dice " reescribir expresión por almacenamiento en caché en precedencia, a continuación, siempre procesarlo de izquierda a derecha". Así que infix (1 + 2) * 3 se convierte en un postfix 12+3*. POST porque el operador se coloca siempre DESPUÉS de los operandos.

2). Evaluación de la expresión postfix. Sencillo. Leer números de la cadena postfix. Empujarlos en una pila hasta que un operador se ve. Comprobar operador tipo-unary? binario? terciario? Pop tantos operandos fuera de la pila como sea necesario para evaluar este operador. Evaluar. Empuje el resultado de nuevo en la pila! Y ya casi está. Sigue haciendo así que hasta pila tiene solo una entrada = valor u r buscando.

Vamos a hacer ( 1 + 2 ) * 3 que está en postfix es "12+3*". Lea el primer número = 1. Empújalo sobre stack. Lea a continuación. Número = 2. Empújalo sobre stack. Lea a continuación. Operador. ¿Cuál? +. ¿De qué tipo? Binary = necesita dos operandos. Pop stack twice = argright es 2 y argleft es 1. 1 + 2 es 3. Empuje 3 de nuevo en la pila. Leer a continuación de la cadena postfix. Es un número. 3.Empujar. Lea a continuación. Operador. ¿Cuál? *. ¿De qué tipo? Binario = necesita dos números - > pop apila dos veces. Primero entra en Argright, segunda vez en Argleft. Evaluar la operación - 3 veces 3 es 9.Empuje 9 en la pila. Leer siguiente postfix char. Es nulo. Fin de la entrada. Pop stack onec = esa es tu respuesta.

3). Shunting Yard se usa para transformar la expresión de infijo humana (fácilmente) legible en expresión de postfijo (también humana fácilmente legible después de alguna práctica). Fácil de codificar manualmente. Véanse los comentarios anteriores y net.

¿Hay algún idioma que quieras usar? ANTLR le permitirá hacer esto desde una perspectiva Java. Adrian Kuhn tiene un excelente writeup 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 lo "general" que quieras que sea.

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

En el cual, no creo que una implementación completa sea apropiada para ser pegada aquí. Te sugiero que eches un vistazo a uno de los infames" Dragon book ".

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

Cuando lo tienes en forma de postfijo, entonces es pan comido a partir de entonces, ya que ya entiendes cómo ayuda la pila.

Sugeriría hacer trampa y usar el Algoritmo Shunting Yard. Es un medio fácil de escribir un analizador de tipo calculadora simple y tiene prioridad en cuenta.

Si desea tokenizar correctamente las cosas y tener variables, etc. involucrado entonces me gustaría seguir adelante y escribir un analizador de descenso recursivo como se sugiere por otros aquí, sin embargo, si simplemente requiere un analizador de estilo calculadora, entonces este algoritmo debería ser suficiente: -)

Encontré esto en el PIClist 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 o operador o paréntesis fue representado por un vagón de ferrocarril en un pista. Una tipo de coche se separó a otra pista y el otro continuó recto delante. No recuerdo los detalles (obviamente!), pero siempre lo pensé sería interesante codificar. Esto es cuando estaba escribiendo 6800 (no 68000) código de montaje.

Este es el algoritmo " shunting yard algorythm" y es lo que la mayoría de los analizadores de máquina utilizar. Ver el artículo sobre análisis en Wikipedia. Una manera fácil de codificar el shunting yard algorythm is to use two pila. Una es la pila "push" y el otro el "reducir" o " resultado" pila. Ejemplo:

Pstack = () / / empty rstack = () entrada: 1+2*3 precedencia = 10 / / menor reducir = 0 / / no reducir

Start: token '1': isnumber, put in pstack (push) token'+': isoperador establecer precedencia = 2 si precedencia

Para reducir, pop elementos del empuje apilar y ponerlos en el resultado pila, siempre intercambiar los 2 elementos superiores en pstack si son de la forma "número de operador":

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 tendría ha sido la lectura del token'+' que tiene menor precendece que el '*'ya empujado, por lo que habría hecho:

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

Y luego empujó ' + 'y luego' 3 ' y luego finalmente reducido:

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

Así que la versión corta es: push numbers, al empujar los operadores comprobar el precedencia del operador anterior. Si fue más alto que el del operador eso va a ser empujado ahora, primero reducir, luego empujar la corriente operador. Para manejar parens simplemente guarde la precedencia del'anterior' operador, y poner una marca en el pstack que le dice al algoritmo de reducción a deje de reducir al resolver el interior de un par de pares. El paréntesis de cierre activa una reducción al igual que el final de entrada, y también elimina el abierto paren mark del pstack, y restaura la 'operación anterior' precedencia para que el análisis pueda continuar después del paren de cierre donde se fue fuera. Esto se puede hacer con recursión o sin (pista: utilice una pila para almacenar la precedencia anterior cuando encontrar un '(' ...). El versión generalizada de esto es utilizar un generador de analizador implementado shunting yard algorythm, f.ex. utilizar yacc o bisonte o taccle (tcl análogo de yacc).

Peter

-Adam

He publicado la fuente de un ultra compacto (1 clase, Java Math Evaluator en mi sitio web. Este es un analizador de descenso recursivo del tipo que causó la explosión craneal para el póster de la respuesta aceptada.

Soporta precedencia completa, paréntesis, variables con nombre y funciones de argumento único.

Publiqué un analizador de expresiones basado en el algoritmo de Shunting Yard de Dijkstra, bajo los términos de la Licencia de Apache 2.0:

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

Otro recurso para el análisis de precedencia es la entrada Operator-precedence parser en Wikipedia. Cubre el algoritmo shunting yard de Dijkstra, y un algoritmo alternativo de árbol, pero más notablemente cubre un algoritmo de reemplazo de macro 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;
}

Invócalo como:

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

Que es impresionante en su simplicidad, y muy comprensible.

He implementado un analizador de descenso recursivo en Java en el proyecto MathEclipse Parser. También podría ser utilizado como un Google Web Toolkit módulo

Actualmente estoy trabajando en una serie de artículos construyendo un analizador de expresiones regulares como una herramienta de aprendizaje para patrones de diseño y programación legible. Puedes echar un vistazo a readablecode. El artículo presenta un uso claro del algoritmo shunting yards.

Escribí un analizador de expresiones en F# y blogueé sobre ello aquí. Utiliza el algoritmo shunting yard, pero en lugar de convertir de infix a RPN, agregué una segunda pila para acumular los resultados de los cálculos. Maneja correctamente la precedencia del operador, pero no admite operadores unarios. Escribí esto para aprender F#, no para aprender a analizar expresiones.

Una solución de Python usando pyparsing se puede encontrar aquí. El análisis de la notación de infijos con varios operadores con precedencia es bastante común, por lo que pyparsing también incluye el constructor de expresiones infixNotation (anteriormente operatorPrecedence). Con él puede definir fácilmente expresiones booleanas usando "AND", "OR", "NOT", por ejemplo. O puede expandir su aritmética de cuatro funciones para usar otros operadores, como ! para factorial, o ' % ' para módulo, o añadir operadores P y C para calcular permutaciones y combinado. Puede escribir un analizador de infijos para notación matricial, que incluya el manejo de operadores' -1 'o' T ' (para inversión y transposición). El ejemplo operatorPrecedence de un analizador de 4 funciones (con '!'thrown in for fun) es aquí y un analizador y evaluador más completo 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-izquierda, infijo-derecha 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 solo busca la precedencia de cada operador como aparece. La gente ha estado mencionando analizadores Pratt personalizados o analizadores shunting yard que pueden aceptar entradas ilegales-este no necesita ser personalizado y (a menos que haya un error) no aceptará entradas malas. 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 dejan claro.

Tenga en cuenta que faltan algunos tipos comunes de operadores, por ejemplo, el tipo de operador utilizado para indexar la tabla ie [índice] o llamar a una función función(parámetro-expresión, ...) Voy a agregarlos, pero piense en ambos como operadores postfix donde lo que viene entre los delimitadores ' ['y'] ' o ' ('y') ' se analiza con una instancia diferente del analizador de expresiones. Lamento haber dejado eso fuera, pero la parte postfix está dentro - agregar el resto probablemente casi duplicará el tamaño del código.

Dado que el analizador es solo 100 líneas de código de raqueta, tal vez debería pegarlo aquí, espero que esto no sea más largo que permite stackoverflow.

Algunos detalles sobre decisiones arbitrarias:

Si un operador postfijo 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 tienen operadores postfix de baja precedencia. - por ejemplo: ((data a) (left 1+) (pre 2 not)(data 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 inferior precedencia que + por lo que quieren agrupar en formas incompatibles ya sea como (a + no b!) + c o como a + (no b!+ c) en estos casos, el operador prefijo siempre gana, por lo que el segundo es la forma en que analiza

Los operadores de infix no asociativos están realmente allí para que no tenga que pretender 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 un kludge. Como tal, en este algoritmo, operadores no asociativos negarse 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 pregunta 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 averigüe exactamente qué porque tal 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 que si 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 ser fácilmente codificado 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;
}

_{siguiente libs podría ser útil:yupana - operaciones estrictamente aritméticas;tinyexpr - operaciones aritméticas + funciones matemáticas C + una proporcionada por el usuario;mpc - combinadores de parser}

Explicación

Vamos a capturar la secuencia de símbolos que representan la expresión algebraica. Primero es un número, que es un decimal dígito 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 number o cualquier símbolo que represente la secuencia sum "*" sum.

sum -> number | sum "+" sum

Intente sustituir number en sum "+" sum que será number "+" number que a su vez podría expandirse 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 asemejarnos a un conjunto de reglas de producción _{aka 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 alterar la posición de su regla de producción frente a los demás. Observe la gramática anterior y observe que la regla de producción para * se coloca debajo de + esto obligará a product evaluar antes de sum. La implementación solo combina el reconocimiento de patrones con la evaluación y por lo tanto refleja de cerca 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í se eval term en primer lugar y devolverlo si no hay * caracteres después de _{esta es la izquierda elección en nuestra regla de producción} de lo contrario - evaluar los símbolos después y volver term.value * product.value _{esta es la elección correcta en nuestra regla de producción es decir,term "*" product}