Skip to main content
adicionou 1 caractere ao conteúdo
Fonte Link
Maniero
  • 484,4mil
  • 94
  • 1,3mil
  • 2,2mil

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigownManiero; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigown; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por Maniero; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

replaced http://pt.stackoverflow.com/ with https://pt.stackoverflow.com/
Fonte Link

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigownsugerido por bigown; um exemplo simples - em JavaScript - aquiaqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigown; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigown; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

Fonte Link
mgibsonbr
  • 82,6mil
  • 22
  • 186
  • 334

As maneiras usuais de se resolver esse problema é ou escrevendo um parser (como sugerido por bigown; um exemplo simples - em JavaScript - aqui) que gere uma representação abstrata dos dados, ou talvez convertendo a expressão para a Notação Polonesa Inversa em um processo de parsing mais simples e então avaliando-a (aqui tem um PDF com instruções, em Pascal - não conheço bem a fonte, achei no Google).

A primeira forma é mais flexível (na pergunta relacionada, o resultado foi usado para resolver equações simples do segundo grau), mas a segunda é mais simples. Vou dar uma explicação bem simplificada aqui (pois implementar em C é meio chatinho, ainda mais pra mim que tenho pouca experiência) junto com links para referências de implementação, para que você possa estudá-las mais a fundo.

  1. O objetivo da notação posfixa é passar todos os operadores pro final - e não pro meio - dos seus operandos. Por exemplo a expressão:

    1 + 2 * 3

    Ficaria assim na notação posfixa:

     1 2 3 * +
    

    Já a expressão:

    (1 + 2) * 3

    Ficaria assim:

     1 2 + 3 *
    

    Etc. Para interpretar essas expressões, considere que cada operador se aplica aos dois últimos operandos lidos, retirando-os da lista e substituindo a todos pelo resultado da operação. O operador seguinte faz o mesmo, e o processo continua até que só sobre um único número na lista (mais detalhes adiante).

    Uma vantagem dessa notação é que os parênteses são desnecessários - qualquer expressão pode ser representada de uma forma que o cálculo ocorra na ordem correta desejada.

    • A conversão entre os formatos infixo e posfixo pode ser feita através do algoritmo de shunting-yard.

      Para entendê-lo, considere que cada operador possui tanto uma precedência quanto uma associatividade: vezes aplica antes de mais, por exemplo, e ambos se associam à esquerda. A - B - C se aplica como (A - B) - C e não como A - (B - C), mas A^B^C se aplica como A^(B^C) e não o contrário. Sub-expressões entre parênteses se aplicam antes do resto.

      O algoritmo funciona lendo cada token (número, operador, abre parêntese ou fecha parêntese) da entrada e então colocando-o ou na saída ou em uma pilha. Números vão sempre pra saída. Operadores vão pra pilha, mas antes eles retiram da pilha (mandando pra saída) qualquer operador cuja precedência seja menor ou menor-ou-igual a ele (dependendo da associatividade). Abre parênteses vão pra pilha, e fecha parênteses desmpilha tudo até o abre parênteses correspondente e joga na saída.

        1 + 2 * 3     []
        _ + 2 * 3     []       1
          _ 2 * 3     [+]      1
            _ * 3     [+]      1 2
              _ 3     [+, *]   1 2
                _     [+, *]   1 2 3
                      [+]      1 2 3 *
                      []       1 2 3 * +
      
        (1 + 2) * 3   []
        _1 + 2) * 3   [(]
         _ + 2) * 3   [(]      1
           _ 2) * 3   [(, +]   1
             _) * 3   [(, +]   1 2
              _ * 3   []       1 2 +
                _ 3   [*]      1 2 +
                  _   [*]      1 2 + 3
                      []       1 2 + 3 *
      
        1 + 2*3 / (4 ^ (5+6) )   []
        _ + 2*3 / (4 ^ (5+6) )   []                   1
          _ 2*3 / (4 ^ (5+6) )   [+]                  1
            _*3 / (4 ^ (5+6) )   [+]                  1 2
             _3 / (4 ^ (5+6) )   [+, *]               1 2
              _ / (4 ^ (5+6) )   [+, *]               1 2 3
                _ (4 ^ (5+6) )   [+, /]               1 2 3 *
                  _4 ^ (5+6) )   [+, /, (]            1 2 3 *
                   _ ^ (5+6) )   [+, /, (]            1 2 3 * 4
                     _ (5+6) )   [+, /, (, ^]         1 2 3 * 4
                       _5+6) )   [+, /, (, ^, (]      1 2 3 * 4
                        _+6) )   [+, /, (, ^, (]      1 2 3 * 4 5
                         _6) )   [+, /, (, ^, (, +]   1 2 3 * 4 5
                          _) )   [+, /, (, ^, (, +]   1 2 3 * 4 5 6
                           _ )   [+, /, (, ^]         1 2 3 * 4 5 6 +
                             _   [+, /]               1 2 3 * 4 5 6 + ^
                                 [+]                  1 2 3 * 4 5 6 + ^ /
                                 []                   1 2 3 * 4 5 6 + ^ / +
      

      Exemplo em C no rosettacode.

  2. Para avaliar uma expressão na notação posfixa, é necessário usar uma pilha. Cada elemento lido é empilhado, caso seja um número, e se for um operador ele desempilha dois números e aplica o operador no mesmo:

     1 2 3 * +    []
     _ 2 3 * +    [1]
       _ 3 * +    [1, 2]
         _ * +    [1, 2, 3]
           _ +    [1, (2*3)] -> [1, 6]
             _    [(1+6)]    -> [7]
    
     1 2 + 3 *    []
     _ 2 + 3 *    [1]
       _ + 3 *    [1, 2]
         _ 3 *    [(1+2)] -> [3]
           _ *    [3, 3]
             _    [(3*3)] -> [9]
    
     1 2 3 * 4 5 6 + ^ / +   []
     _ 2 3 * 4 5 6 + ^ / +   [1]
       _ 3 * 4 5 6 + ^ / +   [1, 2]
         _ * 4 5 6 + ^ / +   [1, 2, 3]
           _ 4 5 6 + ^ / +   [1, (2*3)] -> [1, 6]
             _ 5 6 + ^ / +   [1, 6, 4]
               _ 6 + ^ / +   [1, 6, 4, 5]
                 _ + ^ / +   [1, 6, 4, 5, 6]
                   _ ^ / +   [1, 6, 4, (5+6)] -> [1, 6, 4, 11]
                     _ / +   [1, 6, (4^11)] -> [1, 6, 4194304]
                       _ +   [1, (6/4194304)] -> [1, 0.00000143]
                         _   [(1+0.00000143)] -> [1.00000143]
    

    Exemplo em C no rosettacode.