Calculando com o sed – Parte I

Postado em por

0

Introdução

Durante esse novo ano produzirei uma série de postagens focando no uso do sed como calculadora. Assim veremos como realizar operações de soma, subtração e multiplicação com números decimais e inteiros tudo isso usando o bom e velho comando sed.

Como sabemos, o sed é somente um aplicativo de tratamento de texto, impossibilitando, por exemplo, de forma natural, seu uso para operações matemáticas. Porém, isso não impediu que várias pessoas encontrassem modos elegantes e inteligentes para transformarem scripts sed em potentes calculadoras (veja dc.sed em [1]).

Essa é a Parte I desse tutorial. As demais partes estarão disponíveis nos links abaixo assim que forem postadas:

O conteúdo não está completamente definido e por isso poderá sofrer mudanças no decorrer das postagens.

Soma um

Nosso primeiro objetivo é somar uma unidade a um número qualquer. O modo mais inocente de se fazer isso é:

$ cat soma1_1.sed
#!/bin/sed -f
s/8$/9/
s/7$/8/
s/6$/7/
s/5$/6/
s/4$/5/
s/3$/2/
s/1$/2/
s/0$/1/

A ordem das substituições é importante para evitar substituições em cadeia. Esse método é inocente por não abordar todos os casos. Por exemplo, ele não cobre uma soma em um número terminado em 9 porque para fazer isso, teremos que bolar um jeito para propagarmos o vai um.

Lookup tables

Lookup tables é um recurso bastante utilizado na computação em geral. Essas tabelas armazenam pré-computações que são utilizadas para aumentar o desempenho de certas operações. Para nossos objetivos, essas tabelas funcionarão como vetores que armazenarão números utilizados na operação de somar um.

Acrescentando-se a sequência ;0123456789 após um número, podemos realizar uma soma utilizando somente uma expressão regular:

$ cat soma1_2.sed
#!/bin/sed -f

s/$/;0123456789/
s/\(.\);.*\1\(.\).*/\2/

Todo aquele código em soma1_1.sed foi substituído por apenas duas linhas. Veja que o problema dos vai-uns ainda não foi resolvido.

Vamos testar:

$ chmod +x soma1_2.sed
$ echo '55' | ./soma1_2.sed
56
$ echo 2012 | ./soma1_2.sed
2013
$ echo 109020293200 | ./soma1_2.sed
109020293201

Como isso funciona? Basicamente, acrescentamos nossa lookup table no fim do número na primeira substituição. Em seguida, pegamos o último algarismo do número (antes do delimitador ponto e vírgula) e procuramos na lookup table o número que precede esse último algarismo. Esquematicamente funciona assim:

s/  \(.\)  ; .*\1  \(.\)  .*/   \2/
     ^^^      ^^^   ^^^   ^^^   ^^^
     [1]      [2]   [3]   [4]   [5]

[1] Último algarismo do número
[2] Casamos tudo até o algarismo em [1]
[3] Obtemos o algarismo que precede [1]
[4] Limpamos o restante da lookup table
[5] Substitui último algarismo+lookup table por [3]

Repare que a lookup table desaparece do resultado final porque ela foi completamente casada na substituição.

Intuição geral na Soma Um

O scripts que vimos não cobrem todos os casos por não tratar os vai-uns. Vamos analisar, através de exemplos, como funciona uma soma um em diversos números.

5 --> 6
0 --> 1
123 --> 124
675 --> 676
9 --> 10
19 --> 20
229 --> 230
9999 --> 10000

Você conseguiu perceber um padrão? Podemos ver que se um número não termina em nove, somente o último algarismo dele é incrementado. O problema é quando temos um número terminado em 9. O que acontece nesse caso é: o nove final é transformado em zero e o número anterior que é incrementado. Podemos ver isso nas 4 últimas linhas.

Porém, há ainda dois casos especiais aqui: um é quando temos mais de um 9 final, pois nesse caso o vai-um deve ser propagado em mais de uma casa. Observando a última linha do exemplo, vemos que temos que substituir todos os noves finais por zeros e incrementar o primeiro número (não 9) à esquerda dos noves. O outro caso especial é quando não temos esse número não 9 no número.

Observando padrões podemos chegar a seguinte conclusão em relação a Soma Um em um número:

Se o número NÃO termina em 9
   Incremente o último algarismo. Fazemos isso facilmente
   com lookup tables.

Se o número termina em 9
   Troque todos os 9 finais por zeros e incremente
   o primeiro número não 9 à esquerda dos 9's.

A boa notícia é que podemos englobar esses dois casos usando uma mesma expressão regular.

Montando a expressão regular

Com o que vimos já é o suficiente para montarmos nossa expressão regular final. Devido aos números que terminam com vários noves, teremos que modificar nossa lookup table:

s/$/;9876543210 99990000 999000 9900 90/

Incluímos, agora, uma quantidade fixa de noves e zeros no fim da tabela. Se um número terminar, por exemplo, com três noves, tudo que devemos fazer é encontrar os três noves na tabela e obter a mesma quantidade de zeros. Esse acréscimo na look up é uma maneira inteligente de se mapear os noves na quantidade de zeros correspondente.

Você deve ter reparado que a sequência numérica está invertida. Isso aconteceu devido a particularidade dos números que só contêm noves. A ideia é trocar a expressão .*\1 (veja soma1_2.sed) por [^1]*\(.\)\1 para garantirmos que se mesmo não havendo um número antes dos noves, o algarismo 1 seja sempre obtido.

A nova regexp, então, fica:

$ cat soma1_3.sed
#!/bin/sed -f

s/$/;9876543210 99990000 999000 9900 90/
s/\([0-8]\{0,1\}\)\(9*\);[^1]*\(.\)\1.*\2\(0*\).*/\3\4/

Testando:

$ chmod +x soma1_3.sed
$ echo '999' | ./soma1_3.sed
1000
$ echo '123499' | ./soma1_3.sed
123500

Agora, vamos analisar a última linha do código esquematicamente:

s/\([0-8]\{0,1\}\)  \(9*\) ; [^1]*\(.\)\1  .*\2\(0*\)  .* /  \3\4/
  ^^^^^^^^^^^^^^^^   ^^^^    ^^^^^^^^^^^^    ^^^^^^^^  ^^    ^^^^
      [1]             [2]       [3]            [4]     [5]    [6]

Em [1] armazenamos no retrovisor \1 o algarismo não nove mais à direita do número. Se esse número não existir, ou seja, um número composto somente de noves, o retrovisor terá valor nulo. Em seguida, obtemos os noves finais do número e os armazenamos no retrovisor \2. Mais uma vez, se os noves não existirem, o retrovisor terá valor nulo. Já em [3], guardamos no retrovisor \3 o algarismo que precede o \1. Veja que, pela montagem da expressão, se \1 for nulo, teremos em \3 o algarismo “1”, como queríamos. O próximo passo é a obtenção dos zeros equivalentes. Isso é feito em [4] onde \2 mapeia os noves na lookup table e o \(0*\) armazena no retrovisor \4 o número de zeros correspondente. Por fim, em [5] limpamos o que sobrou da lookup table e em [6] realizamos a substituição de tudo após o algarismo não nove mais à direita por \3 (algarismo incrementado) + \4 (quantidade de zeros equivalente).

O único problema dessa abordagem é que a lookup table é sempre fixa e isso determina um valor máximo de noves finais que um número poderá ter.

Aumentando a precisão da lookup table

A lookup table, como foi elaborada, sempre é fixa e limita o número de noves finais que um número deve ter. Se quisermos, por exemplo, tratar números com até 6 noves finais, teremos que fazer:

s/$/;9876543210 999999000000 9999900000 99990000 999000 9900 90/

Quanto mais noves adicionais, maior ficará a lookup table. Há um modo de aumentarmos a precisão da tabela, ainda mantendo-a fixa, em um taxa melhor que a anterior, ou seja, conseguimos uma maior precisão na entrada sem acrescentarmos muitos caracteres nela.

A ideia é um pouco matemática e você deve limitar a quantidade de noves finais dentro do código. A nova lookup table é a seguinte:

s/$/;9876543210 99999999999;9999999999900000000000/

Com essa tabela, poderemos tratar um número com no máximo 11 noves finais. Obviamente, esse limite poderá ser aumentado simplesmente aumentando os noves antes e depois do ‘;’ e também os zeros, tudo na mesma quantidade.

Como exemplo, considere um número com três noves finais. Mapeamos esses três noves na primeira sequência de noves e obtemos o restante dos noves até o segundo delimitador dois pontos. Isso é, como temos 11 noves nessa sequência, sobrarão agora somente oito (11-3=8). Em seguida, mapeamos esses oito noves na segunda sequência e contamos mais 11 caracteres para avançarmos até a sequência de zeros. A quantidade de zeros restante é a quantidade desejada para a substituição.

Esquematicamente, temos:

99999999999;9999999999900000000000
   ^^^^^^^^ ^^^^^^^^+---------+^^^
      |________|     11 chars   |__ quantidade desejada
          |
      deslocamento de 8 (11-3)

O código geral também deve ser mudado. Não darei maiores explicações, pois deixarei para o leitor tirar suas próprias conclusões. :-)

$ cat soma1_4.sed
#!/bin/sed -f

s/$/;9876543210 99999999999;9999999999900000000000/
s/\([0-8]\{0,1\}\)\(9*\);[^1]*\(.\)\1[^9]*\2\(9*\);\4.\{11\}\(0*\)/\3\5/

Precisão ilimitada

Usando-se de loops podemos alcançar uma precisão ilimitada no processo de Soma Um, e com isso somarmos praticamente qualquer número de entrada.

O que nos impedia de tratarmos qualquer número de entrada era o problema dos noves finais. Sendo assim, trataremos esse problema de outra maneira: trocaremos os noves finais por ‘@’ e, em seguida, incrementaremos o algarismo antes do ‘@’, e assim, no fim do processo, fazemos a troca de ‘@’ por ‘0’.

Em código, fica assim:

$ cat soma1_5.sed
#!/bin/sed -f

:loop ; s/9\b/@/ ; tloop

s/$/;9876543210/
s/\([0-8]\{0,1\}\)\(@*\);[^1]*\(.\)\1.*/\3\2/

y/@/0/

O loop inicial troca os noves finais por @. A lookup table de incremento é adicionada logo em seguida e o número antes do @ é incrementado. Por fim, trocamos os ‘@’s por ‘0’s.

Testando:

$ chmod +x soma1_5.sed
$ echo '19999999999999' | ./soma1_5.sed
20000000000000
$ echo '9999995999999999999' | ./soma1_5.sed 
9999996000000000000

Conclusão

Essa é a Parte I da série ensinando técnicas de cálculo com o SED. As demais partes serão linkadas com essa assim que forem postadas.

Referências

[1] dc.sed – an arbitrary precision RPN calculator by Greg Ubben (Acessado em: Janeiro/2013)
http://sed.sourceforge.net/grabbag/scripts/dc.sed

[2] greg_add.txt by Greg Ubben (Acessado em: Janeiro/2013)
http://sed.sourceforge.net/grabbag/tutorials/greg_add.txt

[3] Lookup Tables & Incrementando em sed by Thobias Salazar Trevisan (Acessado em: Janeiro/2013)
http://thobias.org/doc/lookup_tables_sed.html

Deixe um comentário