elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Proyecto calculadora: Convertir infijo a posfijo.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Proyecto calculadora: Convertir infijo a posfijo.  (Leído 25,671 veces)
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Proyecto calculadora: Convertir infijo a posfijo.
« en: 22 Marzo 2014, 23:56 pm »

Hola a todos. Mi idea a mediano plazo es construir una calculadora "en linea", o sea por consola. No funcionaría con botones, sino que el usuario debe escribir una expresión algebraica, e.g. 2 + 3*(3-6)^2 la cual será evaluada. En el futuro, incluir funciones trigonométricas, exponenciales, etc., lo cual no debe ser difícil una vez se tenga la estructura básica funcionando. Quizá hasta con la opción de graficar. Es un proyecto bonito, porque al estar desarrollado en C estándar, se pudiera incluso compilar en un microprocesador de bajo costo (compatible con C) y hacer así una calculadora científica. Claro, esto sería bien en el futuro pero con algo hay que comenzar.

El primer reto a que debemos enfrentarnos es el tema de conversión de la notación "infija a posfija". Explico a continuación (es un poco extenso, los impacientes favor ir a dar una vuelta, jeje):

Para los humanos es natural la notación 'infija', donde el operador va en medio de los operandos: "5 + 2*3". En cambio para la máquina es natural la notación 'posfija' donde primero van los operandos y luego el operador. Esto es así porque a nivel de máquina primero deben copiarse los argumentos en los registros adecuados del procesador, y luego invocar la instrucción de suma (binaria).  En posfijo, la anterior expresión se escribiría como:

5 2 3 * +

y obśervese como primero debe ejecutarse el operador de mayor prioridad *, y luego +, para cumplir adecuadamente con la asociatividad implícita 5 + (2 * 3).

Ya encontré un algoritmo que explica cómo hacer el paso de una notación a la otra usando pilas, pero más que repetirlo textualmente quisiera encontrarle la lógica. Supóngase que tenemos una expresión del tipo:

A op1 B op2 C

donde A, B, C son los operandos, mientras op1 y op2 son operadores. A menos que existan paréntesis explícitos, la asociatividad viene determinada por la precedencia de dichos operadores. Ahora, disponemos de uns string para la notación infija, un string para la posfija (que debemos ir rellenando) y una pila para ir depositando algunos elementos transitorimente.

Caso 1.  Si op1 tiene mayor precedencia que op2, ejemplo "A * B + C", primero debe evaluarse el resultado de op1, luego el de op2. Entonces, copiamos A al string de posfijo, metemos op1 en la pila, copiamos B al string posfijo, sacamos op1 de la pila y lo pasamos al posfijo, metemos op2 en la pila, copiamos C al string posfijo, sacamos op2 de la pila y lo pasamos al string. Para explicarlo más claramente en forma de tabla.

Paso    |    Pila    |    Posfijo
-------------------------------------
 1      |            |    A
 2      |     op1    |   
 3      |            |    A B
 4      |     op2    |    A B op1         <-- sacamos op1 de la pila y lo pasamos al string
 5      |     op2    |    A B op1 C       
 6      |            |    A B op1 C op2

Caso 2.  Cuando op1 y op2 tienen igual precedencia, ejemplo "A + B + C". En este caso, la asociatividad debe ser de izquierda a derecha "(A + B) + C", por lo que se evalúa primero op1 y luego op2. Se procede exactamente de la misma manera que en el caso 1.

Caso 3.  Cuando op1 es de menor prioridad que op2, ejemplo "A + B * C". Aquí debe evaluarse "A + (B * C)". Esto significa que op1 debe esperar por el resultado de op2, el string posfijo deberá quedar "A B C op2 op1". En forma de tabla:

Paso    |    Pila    |    Posfijo
-------------------------------------
 1      |            |    A
 2      |     op1    |   
 3      |            |    A B
 4      |  op1, op2  |    A B           <-- no se saca op1 al momento de colocar op2
 5      |            |    A B op2 op1   <-- vaciamos la pila

La diferencia con el caso 1 es que al momento de introducir op2 en la pila, no se saca antes op1. Esto es porque op2 tiene mayor precedencia que op1 entonces debe evaluarse primero, es decir, debe quitarse primero op2 de la pila y luego op1.

Uno puede resumir diciendo que al momento de colocar un nuevo operador en la pila, se sacan todos los operadores anteriormente depositados y que tengan mayor o igual jerarquía a la suya (y que deben evaluarse antes), estos operadores son pasados al string posfijo y el nuevo operador es depositado en la pila.

Con esta explicación precedente, se puede presentar el algoritmo para convertir infijo a posfijo. Debemos leer la expresión infija de izquierda a derecha y luego

* Los espacios son despreciados.
* Si el argumento leido es un operando (número), pasarlo al string posfijo.
* Si el argumento leido es un operador entonces:
  - Si la pila no está vacía, retirar todos los operadores con una precedencia
    mayor o igual al operador actual y pasarlos al posfijo, en el orden en que son retirados.
  - Colocar el nuevo operador en la pila.
* Si se lee un paréntesis izquierdo '(', depositarlo en la pila.
* Si se lee un paréntesis derecho ')', retirar de la pila todos los elementos hasta encontrar
  un '('. Dichos elementos son pasados al posfijo, menos el paréntesis '(' que es descartado.
* Al finalizar el proceso, pasar al posfijo cualquier elemento que haya quedado en la pila.

Entonces me puse manos a la obra. El programa está hecho en C++, que al usar clases STL se simplifica bastante (estoy pensando una versión en C puro, con código más elemental, útil quizás si se piensa migrar a un hardware más básico como un uC).

El programa recibe una cadena de notación infija y la convierte a posfija. Para propósitos de depuración se dan mensajes en pantalla sobre los pasos que van efectuando (funcionalidad que se debe quitar más adelante). Al final, evalúa el resultado y lo imprime. Por ejemplo, una cadena sencilla como:

5 + 2 * 3

produce la salida:
Código:
Intro expresion infija: 5 + 2 * 3

Analizando token: '5'
es numero: pasado a posfijo

Analizando token: '+'
es operador:
colocar '+' en la pila

Analizando token: '2'
es numero: pasado a posfijo

Analizando token: '*'
es operador:
colocar '*' en la pila

Analizando token: '3'
es numero: pasado a posfijo

Pasado operador '*' de la pila a posfijo

Pasado operador '+' de la pila a posfijo

Posfijo es:
5 2 3 * +

Evaluando la expresion ...
operar 2*3 = 6
operar 5+6 = 11
El resultado es: 11

y un caso más complicado:

5 + 3*(4 - 7)^2 - 1

produce:
Código:
Analizando token: '5'
es numero: pasado a posfijo

Analizando token: '+'
es operador:
colocar '+' en la pila

Analizando token: '3'
es numero: pasado a posfijo

Analizando token: '*'
es operador:
colocar '*' en la pila

Analizando token: '('
pasado a posfijo

Analizando token: '4'
es numero: pasado a posfijo

Analizando token: '-'
es operador:
colocar '-' en la pila

Analizando token: '7'
es numero: pasado a posfijo

Analizando token: ')'
pasado operador '-' de la pila a posfijo

Analizando token: '^'
es operador:
colocar '^' en la pila

Analizando token: '2'
es numero: pasado a posfijo

Analizando token: '-'
es operador:
pasado operador '^' de la pila a posfijo
pasado operador '*' de la pila a posfijo
pasado operador '+' de la pila a posfijo
colocar '-' en la pila

Analizando token: '1'
es numero: pasado a posfijo

Pasado operador '-' de la pila a posfijo

Posfijo es:
5 3 4 7 - 2 ^ * + 1 -

Evaluando la expresion ...
operar 4-7 = -3
operar -3^2 = 9
operar 3*9 = 27
operar 5+27 = 32
operar 32-1 = 31
El resultado es: 31

A continuación el código fuente, que es el trabajo de unas horas repartidas entre ayer y hoy:
Código
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <string>
  4. #include <stack>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. /* Operadores matematicos */
  10. #define N_operators 6
  11. const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};
  12. int precedences[N_operators] = {1, 1, 2, 2, 2, 3};
  13.  
  14. bool is_operator( const string );
  15. int precedence( const string );
  16.  
  17. /* Mis sugerencias personales a este programa:
  18.  *
  19.  * - Considerar el cambio del nombre standby por aux_stack, u otro.
  20.  * - Incorporar el analizador lexico para expresiones numericas de punto
  21.  *   flotante, o que ocupen mas de un caracter.
  22.  * - Eliminar la cadena intermedia postfix, pasando directamente los
  23.  *   resultados de la pila de operadores extraidos de infix, a una pila
  24.  *   de evaluacion.
  25.  * - Incorporar operadores unarios, como sin(), cos(), exp(), log(), etc.
  26.  * - Detectar errores de sintaxis en la expresion infija.
  27.  * - Otros que sean recomendados.
  28.  */
  29.  
  30. int main() {
  31.  
  32. string infix, postfix, token;
  33. stack <string> standby;
  34. stack <double> result;
  35. size_t i;
  36. char c;
  37. double A, B;
  38.  
  39. /* Cadena de entrada */
  40. cout << "Intro expresion infija: ">
  41. getline( cin, infix );
  42. cout << endl;
  43.  
  44. /*************************************************************
  45.  PRIMERA PARTE: Procesar la cadena infijo, y crear posfijo
  46. *************************************************************/
  47. for ( i = 0; i < infix.size(); i++ ) {
  48. /* esto debe cambiar luego a un token o palabra devuelta por
  49. * el analizador léxico */
  50. c = infix[i];
  51. token.clear();
  52. token += c; /* parece burdo, pero no conozco mejor manera de
  53. * crear un string a partir de un unico caracter */
  54.  
  55. /* es un espacio: despreciar */
  56. if ( c == ' ' ) continue;
  57.  
  58. cout << "Analizando token: '" << c << "'" << endl;
  59.  
  60. /* es un carácter numérico: pasar al posfijo */
  61. if ( c >= '0' && c <= '9' ) {
  62. cout << "\tes numero: pasado a posfijo" << endl << endl;
  63. postfix = postfix + " " + c;
  64. continue;
  65. }
  66.  
  67. /* si se lee un operador: sacar de la pila y pasar al postfijo
  68. * todos los operadores con una precedencia mayor o igual a la
  69. * suya, y depositar el mismo en la pila */
  70. if ( is_operator( token ) ) {
  71. cout << "\tes operador:" << endl;
  72. while ( !standby.empty() && precedence( standby.top() )
  73. >= precedence( token ) ) {
  74. cout << "\tpasado operador '" + standby.top() +
  75. "' de la pila a posfijo" << endl;
  76. postfix = postfix + " " + standby.top();
  77. standby.pop();
  78. }
  79. standby.push( token );
  80. cout << "\tcolocar '" << token << "' en la pila" << endl << endl;
  81. continue;
  82. }
  83.  
  84. /* si se lee "(": colocar en la pila */
  85. if ( token == "(" ) {
  86. cout << "pasado a posfijo" << endl << endl;
  87. standby.push( token );
  88. continue;
  89. }
  90.  
  91. /* si se lee ")": retirar de la pila hasta encontrar '(', y pasar
  92. * los elementos retirados a posfijo, luego descartar el "(" */
  93. if ( token == ")" ) {
  94. while ( !standby.empty() && standby.top() != "(" ) {
  95. cout << "\tpasado operador '" + standby.top() +
  96. "' de la pila a posfijo" << endl << endl;
  97. postfix = postfix + " " + standby.top();
  98. standby.pop();
  99. }
  100. if ( !standby.empty() )
  101. standby.pop(); /* descartar el "(" */
  102. }
  103. }
  104.  
  105. /* extraer de la pila cualquier operador restante y pasarlo a la cadena posfijo */
  106. while ( !standby.empty() ) {
  107. cout << "Pasado operador '" + standby.top() +
  108. "' de la pila a posfijo" << endl << endl;
  109. postfix = postfix + " " + standby.top();
  110. standby.pop();
  111. }
  112.  
  113. /* Imprimir el posfijo */
  114. cout << "Posfijo es: \n\t" << postfix << endl << endl;
  115.  
  116. /****************************************************************
  117.  SEGUNDA PARTE: Procesar la cadena posfijo, y devolver resultado
  118. ****************************************************************/
  119.  
  120. A = 0;
  121. cout << "Evaluando la expresion ..." << endl;
  122. for ( i = 0; i < postfix.size(); i++ ) {
  123.  
  124. c = postfix[i];
  125. token.clear();
  126. token += c;
  127.  
  128. /* si se lee un operando (caracter numerico), depositar en la pila */
  129. if ( c >= '0' && c <= '9' ) {
  130. result.push( c - '0' );
  131. continue;
  132. }
  133.  
  134. /* si se lee un operador binario, poner en A y B los últimos dos argumentos
  135. * de la pila y operarlos, guardando el resultado en la pila */
  136. if ( is_operator( token ) ) {
  137. if ( !result.empty() ) {
  138. B = result.top();
  139. result.pop();
  140. }
  141. else {
  142. cout << "Argumentos insuficientes para '" << c << "'" << endl;
  143. return -1;
  144. }
  145.  
  146. if ( !result.empty() ) {
  147. A = result.top();
  148. result.pop();
  149. }
  150. else {
  151. cout << "Argumentos insuficientes para '" << c << "'" << endl;
  152. return -1;
  153. }
  154.  
  155. cout << "\toperar " << A << token << B << " = ";
  156. if ( token == "+" ) {
  157. A += B;
  158. result.push( A );
  159. }
  160. else if ( token == "-" ) {
  161. A -= B;
  162. result.push( A );
  163. }
  164. else if ( token == "*" ) {
  165. A *= B;
  166. result.push( A );
  167. }
  168. else if ( token == "/" ) {
  169. A /= B;
  170. result.push( A );
  171. }
  172. else if ( token == "%" ) {
  173. A = (int )A % (int )B;
  174. result.push( A );
  175. }
  176. else if ( token == "^" ) {
  177. A = pow(A, B);
  178. result.push( A );
  179. }
  180. cout << A << endl;
  181. }
  182. }
  183.  
  184. if ( !result.empty() )
  185. cout << endl << "El resultado es: " << result.top() << endl;
  186.  
  187. return 0;
  188. }
  189.  
  190. /* Verdadero si el token corresponde a un operador. */
  191. bool is_operator( const string token ) {
  192.  
  193. for ( int i = 0; i < N_operators; i++ )
  194. if ( operators[i] == token )
  195. return true;
  196.  
  197. return false;
  198. }
  199.  
  200. /* Devuelve la precedencia del operador descrito por el
  201.  * string token (-1 si no es un operador) */
  202. int precedence( const string token ) {
  203.  
  204. for ( int i = 0; i < N_operators; i++ )
  205. if ( operators[i] == token )
  206. return precedences[i];
  207.  
  208. return -1;
  209. }


En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #1 en: 23 Marzo 2014, 00:22 am »

¡Hey! ¡Que recuerdos!

Yo también hize una calculadora de esas en mis tiempos, la mía además hacía funciones matematicas (sin,cos,tan,log,sqrt... todas recreadas con la libreria estandar y a correr xD). También tenía algunas macros como el número pi o el numero de euler. Lo que más me costo son los anidamientos así:
Citar
sin(sin(2))

Aunque yo no usaba pila, sino un enfoque más simplista: "Divide y venceras". Si tenía la siguiente expresión:

Citar
2 + 3 * 2

La transformaba:
Citar
2 + 6

Y la volvía a reinterpretar.

El código es de hace 1 año casi, mucho ha llovido desde entonces. Hay muchísimas cosas que haría de otra forma (como la función convertirnumero, que tiene bastantes aberraciones ;D).

Código
  1. #include <iostream>
  2. #include <cmath>
  3. #include <list>
  4. #include <sstream>
  5. #include <map>
  6.  
  7. /** Fecha: 05/07/2013
  8.  
  9. Analiza una expressión en formato texto y resuelve las operaciones pertinentes
  10.  
  11. */
  12.  
  13. const int MAX =5;
  14.  
  15. using namespace std;
  16.  
  17. inline void ResolverParentesis(string &Entrada,short &i);
  18. double Ejecucion(string &Entrada);
  19. double ConvertirNumero(string &Entrada,int &Index);
  20. double RealizarOperacion(string &Entrada);
  21. int ObtenerOperadorAnterior(string &Entrada,int Index);
  22. double RealizarOperacion(string &Entrada);
  23.  
  24. double ConvertirAngulo(double Entrada)
  25. {
  26.    return Entrada *3.141592/180;
  27. }
  28.  
  29. inline void ResolverFunciones(string& Entrada);
  30.  
  31. const char Operaciones[MAX] = {'^','/','*','+','-'};
  32.  
  33. typedef double (*Puntero_A_Funcion)(double);
  34.  
  35. map<string,Puntero_A_Funcion> Punteros;
  36. map<string,double> Macros;
  37.  
  38. int main()
  39. {
  40.    Punteros["sin"] = sin;
  41.    Punteros["cos"] = cos;
  42.    Punteros["tan"] = tan;
  43.  
  44.    Punteros["sinh"] = sinh;
  45.    Punteros["cosh"] = cosh;
  46.    Punteros["tanh"] = tanh;
  47.  
  48.    Punteros["asin"] = asin;
  49.    Punteros["acos"] = acos;
  50.    Punteros["atan"] = atan;
  51.  
  52.    Punteros["asinh"] = asinh;
  53.    Punteros["acosh"] = acosh;
  54.    Punteros["atanh"] = atanh;
  55.  
  56.    Punteros["cbrt"] = cbrt;
  57.    Punteros["sqrt"] = sqrt;
  58.  
  59.    Punteros["log"] = log;
  60.    Punteros["log10"] = log10;
  61.  
  62.    Punteros["abs"] = abs;
  63.  
  64.    Punteros["rad"] = ConvertirAngulo;
  65.  
  66.    Macros["pi"] = 3.141592654;
  67.    Macros["euler"] = 2.7182818;
  68.    Macros["aureo"] = 1.61803398;
  69.    Macros["ans"] = 0;
  70.  
  71.    string Expresion;
  72.    cout<<"Calculadora parser por amchacon"<<endl<<endl;
  73.  
  74.    cout<<"Soporte para las siguientes funciones matematicas: "<<endl<<endl;
  75.  
  76.    short Contador = 0;
  77.  
  78.    for (auto it = Punteros.begin(); it != Punteros.end(); it++)
  79.    {
  80.        cout<<it->first<<"\t";
  81.        Contador++;
  82.        if (Contador == 3)
  83.        {
  84.            Contador = 0;
  85.            cout<<endl;
  86.        }
  87.    }
  88.  
  89.    cout<<endl<<endl<<"Constantes definidas: "<<endl;
  90.  
  91.    Contador = 0;
  92.    for (auto it = Macros.begin(); it != Macros.end(); it++)
  93.    {
  94.        cout<<it->first<<"\t";
  95.        Contador++;
  96.        if (Contador == 3)
  97.        {
  98.            Contador = 0;
  99.            cout<<endl;
  100.        }
  101.    }
  102.  
  103.    cout<<endl<<endl;
  104.  
  105.    while(1)
  106.    {
  107.  
  108.        cout << "Introduce tu expresion: " << endl;
  109.        getline(cin,Expresion);
  110.  
  111.        try
  112.        {
  113.            cout<<endl<<"El resultado es: "<<RealizarOperacion(Expresion);
  114.        }
  115.        catch(const char* c)
  116.        {
  117.            cout<<endl<<c;
  118.        }
  119.  
  120.        cout<<endl<<endl<<endl;
  121.  
  122.    }
  123.    return 0;
  124. }
  125.  
  126. double RealizarOperacion(string &Entrada)
  127. {
  128.    int Index;
  129.  
  130.    if (Entrada.empty())
  131.        throw "Error, expresion vacia";
  132.  
  133.    // Macros
  134.  
  135.    for (auto it = Macros.begin();it != Macros.end();it++)
  136.    {
  137.        Index = Entrada.find(it->first);
  138.  
  139.        if (Index != -1)
  140.        {
  141.            Entrada.erase(Index,it->first.size());
  142.            stringstream Cosita;
  143.            Cosita<<it->second;
  144.            Entrada.insert(Index,Cosita.str());
  145.        }
  146.    }
  147.  
  148.    // Funciones matemáticas
  149.  
  150.    ResolverFunciones(Entrada);
  151.    Macros["ans"] =  Ejecucion(Entrada);
  152.  
  153.    return Macros["ans"];
  154. }
  155.  
  156. /** Función principal que resuelve la operación **/
  157.  
  158. double Ejecucion(string &Entrada)
  159. {
  160.    // Comprobando paréntesis
  161.  
  162.    for (short i = 0; i < Entrada.size(); i++)
  163.    {
  164.        if (Entrada[i] == '(') // Si hay un parentesis
  165.        {
  166.            ResolverParentesis(Entrada,i);
  167.        }
  168.    }
  169.  
  170.    /** Empezamos a resolver las operaciones **/
  171.  
  172.    for (short j = 0; j < MAX; j++) // Recorremos las 4 operaciones
  173.        for (short i = 0; i < Entrada.size(); i++)
  174.        {
  175.            if (Entrada[i] == Operaciones[j]) // Si encontramos nuestra operación
  176.            {
  177.                int Inicio = ObtenerOperadorAnterior(Entrada,i); // Buscamos el operador que le precede (o el 0)
  178.  
  179.                if (Inicio == -1)
  180.                    continue;
  181.  
  182.                int Index = Inicio; // El index es nuestra posicion actual
  183.                int Tam = Index; // El tamanyo de la expresion que contiene nuestra operacion
  184.                double Operacion = ConvertirNumero(Entrada,Index); // Obtenemos el primer numero
  185.  
  186.                // Eliminando espacios en blanco...
  187.  
  188.                while(Entrada[Index] == ' ')
  189.                {
  190.                    Index++;
  191.                }
  192.  
  193.                Index++; // Eliminamos el operador
  194.  
  195.                double Numerito = ConvertirNumero(Entrada,Index); // Obtenemos el segundo numero de la operacion
  196.  
  197.                switch (j) // Dependiendo de la operacion que estabamos buscando hacemos una cosa o otra
  198.                {
  199.                case 0:
  200.                    Operacion = pow(Operacion,Numerito);
  201.                    break;
  202.                case 1:
  203.                    if (!Numerito)
  204.                        throw "Error, division por cero";
  205.                    Operacion /= Numerito;
  206.                    break;
  207.                case 2:
  208.                    Operacion *= Numerito;
  209.                    break;
  210.                case 3:
  211.                    Operacion += Numerito;
  212.                    break;
  213.                case 4:
  214.                    Operacion -= Numerito;
  215.                }
  216.  
  217.                // El tamanyo de nuestra expresión es final (Index) menos inicio
  218.  
  219.                Tam = Index-Inicio;
  220.  
  221.                // Actualizamos nuestra expression
  222.  
  223.                Entrada.erase(Inicio,Tam); // Borramos la antigua
  224.  
  225.                // Obtenemos la expression númerica de la nueva
  226.  
  227.                stringstream Buffer;
  228.                Buffer<<Operacion;
  229.  
  230.                // Y la insertamos
  231.  
  232.                Entrada.insert(Inicio,Buffer.str());
  233.  
  234.                // Volvemos al principio
  235.  
  236.                i = 0;
  237.            }
  238.        }
  239.  
  240.    /** Ahora unicamente nos queda una expresión númerica, la pasamos a número y la devolvemos **/
  241.  
  242.    int Index = 0;
  243.    return ConvertirNumero(Entrada,Index);
  244. }
  245.  
  246. inline void ResolverFunciones(string& Entrada)
  247. {
  248.    int Index;
  249.    for (auto it = Punteros.begin(); it != Punteros.end(); it++)
  250.    {
  251.        Index = Entrada.find(it->first);
  252.        if (Index != -1)
  253.        {
  254.            int Inicio = Index;
  255.            Index = Inicio+it->first.size();
  256.            while(Entrada[Index] == ' ')
  257.            {
  258.                Index++;
  259.            }
  260.            short aux = Index;
  261.            if (Entrada[Index] == '(')
  262.            {
  263.                 ResolverParentesis(Entrada,aux);
  264.            }
  265.  
  266.  
  267.            if ((Entrada[Index] >= '0' && Entrada[Index] <= '9') || (Entrada[Index] == '-') || Entrada[Index] == '+')
  268.            {
  269.                stringstream Cosita;
  270.                Cosita<<it->second(ConvertirNumero(Entrada,Index));
  271.                Entrada.erase(Inicio,Index-Inicio);
  272.                Entrada.insert(Inicio,Cosita.str());
  273.            }
  274.        }
  275.    }
  276. }
  277.  
  278. inline void ResolverParentesis(string &Entrada,short &i)
  279. {
  280.    short Toque = 1; // Buscamos el siguiente parentesis
  281.    string Buffer; // Aquí guardaremos la expresión inscrita en el paréntesis
  282.    bool Correcto = false; // Variable que comprueba si se llego al final del parentesis
  283.  
  284. //    for (auto it = Punteros.begin(); it != Punteros.end(); it++)
  285. //    {
  286. //        if (Entrada)
  287. //    }
  288.  
  289.    for (short j = (i+1); j < Entrada.size(); j++)
  290.    {
  291.        Buffer+= Entrada[j]; // Vamos guardando la expresion...
  292.  
  293.        /** Si encontramos un paréntesis anidado, tendremos que encontrar el siguiente cierre de paréntesis **/
  294.  
  295.        if (Entrada[j] == '(')
  296.            Toque++;
  297.        if (Entrada[j] == ')') // Cierre de parentesis, un parentesis menos que buscar
  298.            Toque--;
  299.  
  300.        if (Toque == 0) // Si ya hemos terminado
  301.        {
  302.            Buffer.erase(Buffer.size()-1,1); // Borramos el ')'
  303.  
  304.            ResolverFunciones(Buffer);
  305.  
  306.            /** Aplicamos recursividad, resolvemos la operación inscrita en el paréntesis **/
  307.  
  308.            Ejecucion(Buffer);
  309.  
  310.            /** Borramos nuestro paréntesis y lo sustituimos por nuestro nuevo valor **/
  311.  
  312.            Entrada.erase(i,j-i+1);
  313.            Entrada.insert(i,Buffer);
  314.            i = 0;
  315.            Correcto = true; // Finalizo correctamente
  316.            break;
  317.        }
  318.    }
  319.  
  320.    if (!Correcto) // Si no se encontró el final del paréntesis
  321.    {
  322.        throw "No se encontro el fin del parentesis \n";
  323.    }
  324. }
  325.  
  326. // Dada la posición de un operador, devuelve la posición contigua del operador anterior (o 0)
  327.  
  328. int ObtenerOperadorAnterior(string &Entrada,int Index)
  329. {
  330.    Index--; // nos saltamos nuestro operador
  331.    if (Index < 0)
  332.        return -1;
  333.  
  334.    // Vamos recorriendo nuestra entrada hasta que lo encontramos
  335.  
  336.    while (Entrada[Index] != '+' && Entrada[Index] != '-' && Entrada[Index] != '*' && Entrada[Index] != '/' && Index != 0)
  337.    {
  338.        Index--;
  339.    }
  340.  
  341.    if (Index != 0)
  342.        return Index+1; // Devolvemos la posición contigua
  343.    else
  344.        return 0;
  345. }
  346.  
  347. /** El santo grial de todo, convierte una expressión de texto en un número **/
  348.  
  349. double ConvertirNumero(string &Entrada,int &Index)
  350. {
  351.    list<double> Enteros;
  352.    list<double> Decimales;
  353.    short aux;
  354.    short signo = 1;
  355.  
  356.    // Nos saltamos los espacios en blanco
  357.  
  358.    while(Entrada[Index] == ' ')
  359.    {
  360.        Index++;
  361.    }
  362.  
  363.    if (Entrada[Index] == '-')
  364.    {
  365.        signo = -1;
  366.        Index++;
  367.    }
  368.  
  369.    /** Ahora debería haber números, de lo contrario tenemos un error **/
  370.  
  371.    if (Entrada[Index] < '0' || Entrada[Index] > '9')
  372.    {
  373.        stringstream buffer;
  374.        buffer<<"Error de sintaxis, desconocido elemento: '"<<Entrada[Index]<<"' en la posicion: "<<Index+1;
  375.        throw buffer.str().c_str();
  376.    }
  377.  
  378.    /** Añadimos los enteros **/
  379.  
  380.    while (Entrada[Index] >= '0' && Entrada[Index] <= '9' && Index < Entrada.size())
  381.    {
  382.        Enteros.push_back(Entrada[Index]-48);
  383.        //cout<<Cosa[i]<<endl;
  384.        Index++;
  385.    }
  386.  
  387.    /** Si a continuación encontramos un punto o una coma, esque hay numeros a continuacion **/
  388.  
  389.    if (Entrada[Index] == '.' || Entrada[Index] == ',')
  390.    {
  391.        bool Activado = false;
  392.        Index++;
  393.        while (Entrada[Index] >= '0' && Entrada[Index] <= '9' && Index < Entrada.size())
  394.        {
  395.            Decimales.push_back(Entrada[Index]-48);
  396.            Index++;
  397.            Activado = true;
  398.        }
  399.        if (!Activado)
  400.        {
  401.            throw "Error de sintaxis, se insertó un punto pero no se añadió ningun decimal";
  402.        }
  403.    }
  404.    double Numero = 0; // El valor que devolveremos
  405.    aux = 0;
  406.  
  407.    /** Recorremos los enteros y lo pasamos a número. Como tenemos las cifras simplemente es sumarlas **/
  408.  
  409.    for (auto it = Enteros.begin(); it != Enteros.end(); it++)
  410.    {
  411.        Numero += *it*pow(10,Enteros.size()-aux-1);
  412.        aux++;
  413.    }
  414.    aux = 0;
  415.  
  416.    /** Idem, pero para los decimales **/
  417.  
  418.    if (!Decimales.empty())
  419.        for (auto it = Decimales.begin(); it != Decimales.end(); it++)
  420.        {
  421.            Numero += *it/(pow(10,(aux))*10);
  422.            aux++;
  423.        }
  424.  
  425.    Numero *= signo;
  426.    return Numero;
  427. }
  428.  

El código en cuestión usa el estándar C++11. Tendrás que activar ese estandar en el compilador.

Creo que tu sistema es mejor, pero podrías utilizar de este código el objeto map que uso para hacer las funciones matemáticas (sin,cos,tan...).

¿Críticas a tú código? Que es muy poco modular.


En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #2 en: 23 Marzo 2014, 00:24 am »

Por ahora la mayor debilidad del programa anterior (inspirado en un ejercicio propuesto en un libro) es que procesa números formados por un solo dígito.

Sucede que dicho programa, aunque en una versión muy reducida, implementa funciones de un compilador. Debe pasar por una fase de análisis léxico, y una de análisis sintáctico.

El análisis léxico consiste en identificar los tokens, elementos léxicos o lexemas, que son las palabras básicas en que se escribe el lenguaje. En nuestro caso, los tokens por los momentos serían:
  • paréntesis
  • números
  • operadores aritméticos binarios: + - * / % ^
  • operadores unarios (por incluir en el futuro): sin(), cos(), exp(), log(), etc.
  • caracteres de espacio, mismos que son ignorados

El análizador léxico pasa sus resultados al analizador sintáctico o parser que en el programa que presenté es el que manejas las pilas de conversión de infijo a postfijo, y la pila de evaluación de resultados.

Lo que requiero por los momentos es una idea para construir un analizador léxico más completo, que reconozca los tokens anteriormente descritos, y sea capaz de entregarlos al parser para su procesamiento. Estos tokens pueden ser monocarácter o multicarácter. El problema mayor se presenta al reconocer los números.

Definiríamos un número como cualquier cadena de caracteres que empiece opcionalmente con un signo '+' ó '-', luego una cadena de caracteres numéricos comprendidos entre '0' y '9', luego opcionalmente un carácter de punto decimal '.', y opcionalmente una cadena de caracteres numéricos para la parte decimal. Queda a criterio del diseñador si quiere considerar expresiones en notación exponencial como 12.34E+5
Serían errores de sintaxis duplicar el carácter de signo, o el carácter de punto decimal, e.g. ++15.7, ó -18.71.3
Obsérvese que la expresión:

3 + +10

se considera correcta, porque "+10" se interpreta como "10". Si embargo, el primer "+" debe ser interpretado como símbolo de suma, mientras el segundo es un signo de positivo. Así que un mismo carácter puede tener distintos significados.

En contraposición, la expresión

3 + + 10

es incorrecta porque el segundo '+' está separado del 10 por un espacio, entonces no se considera signo de positivo, sino símbolo de suma por lo que hay doble suma.

Esta parte entonces, y para lo que invoco la ayuda de la comunidad, debe recibir una cadena en infijo, reconocer los distintos tokens según las reglas ya explicadas, y presentarlos por la salida estándar indicando su tipo y valor. Ejemplo (3.5 + 4.15) * -2^3 debe presentar:

token: (,  tipo parentesis
token: 3.5,  tipo numero
token: +,  tipo suma
token: 4.25,  tipo numero
token: ),  tipo parentesis
token: *,  tipo producto
token: -2,  tipo numero
token: ^,  tipo potenciacion
token: 3,  tipo numero

Favor código claro y legible, no construcciones crípticas. Favor abstenerse personas con una actitud orgullosa que vienen a demostrar que pueden programar de una manera tan incomprensible que sólo se entienden ellos mimos, jaja  :D

Yo mientras, trataré de trabajar en el analizador sintáctico para incorporar los operadores unarios y eliminar la cadena intermedia postfix !!!



Hola amchacon!!! Saludos como siempre!

Investigué un poco sobre el tema y parece que la manera en que ésto se resuelve más comúnmente es con pilas. De hecho, así trabajan los compiladores para traducir código fuente a lenguaje máquina, y casi aseguría que así lo hacen todas las calculadoras (lo aseguro porque es el método que enseñan todos los libros, jeje).

Pero te cuento que hace tiempo y como desconocía el método de las pilas, ideé una solución ad-hoc parecida a la tuya, ... pero como que así resulta más complicado. Fíjate que mi programa no tiene problema con uno o varios niveles de anidamiento, por ejemplo:

2*(1 + 3*( 4 + 5) )

y después de mucho bla bla te dice:
Código:
Posfijo es:
2 1 3 4 5 + * + *

Evaluando la expresion ...
operar 4+5 = 9
operar 3*9 = 27
operar 1+27 = 28
operar 2*28 = 56
El resultado es: 56

Yo creo que incorporar los operadores unarios sin(), cos(), abs(), log(), y las macros que por fortuna vienen definidas en la propia biblioteca de C como M_PI, M_E será una buena idea y no tan difícil.

En mi caso creo que ahorita lo más difícil será analizar léxicamente la expresión para detectar números decimales, signados o no, y por eso acabo de proponer un reto a la comunidad, espero me ayudes con un aporte ...  :D
« Última modificación: 23 Marzo 2014, 06:10 am por Eternal Idol » En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #3 en: 23 Marzo 2014, 01:19 am »

La solución es más fácilita de lo que parece:
Código
  1. /* es un carácter numérico: pasar al posfijo */
  2. if ( c >= '0' && c <= '9' )
  3. {
  4.    cout << "\tes numero: pasado a posfijo" << endl << endl;
  5.    postfix = postfix + " " + c;
  6.    continue;
  7. }
  8.  

Has detectado un número, bien. Aquí debes leer EL NUMERO ENTERO, un ejemplo sería reutilizar mi función:

Código
  1. /* es un carácter numérico: pasar al posfijo */
  2. if ( c >= '0' && c <= '9' )
  3. {
  4.    double aux = ConvertirNumero(infix,i);
  5.    cout << "\tes numero: pasado a posfijo" << endl << endl;
  6.    result.push(aux);
  7.    continue;
  8. }
  9.  

La función ConvertirNumero() te actualiza la posición de tu indice i, asi que no deberías preocuparte por eso. También te lee los decimales.

El código completo sería:

Código
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <string>
  4. #include <stack>
  5. #include <cmath>
  6. #include <list>
  7. #include <sstream>
  8. using namespace std;
  9.  
  10. /* Operadores matematicos */
  11. #define N_operators 6
  12. const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};
  13. int precedences[N_operators] = {1, 1, 2, 2, 2, 3};
  14.  
  15. bool is_operator( const string );
  16. int precedence( const string );
  17.  
  18. /* Mis sugerencias personales a este programa:
  19.  *
  20.  * - Considerar el cambio del nombre standby por aux_stack, u otro.
  21.  * - Incorporar el analizador lexico para expresiones numericas de punto
  22.  *   flotante, o que ocupen mas de un caracter.
  23.  * - Eliminar la cadena intermedia postfix, pasando directamente los
  24.  *   resultados de la pila de operadores extraidos de infix, a una pila
  25.  *   de evaluacion.
  26.  * - Incorporar operadores unarios, como sin(), cos(), exp(), log(), etc.
  27.  * - Detectar errores de sintaxis en la expresion infija.
  28.  * - Otros que sean recomendados.
  29.  */
  30.  
  31. double ConvertirNumero(string &Entrada,int &Index)
  32. {
  33.    list<double> Enteros;
  34.    list<double> Decimales;
  35.    short aux;
  36.    short signo = 1;
  37.  
  38.    // Nos saltamos los espacios en blanco
  39.  
  40.    while(Entrada[Index] == ' ')
  41.    {
  42.        Index++;
  43.    }
  44.  
  45.    if (Entrada[Index] == '-')
  46.    {
  47.        signo = -1;
  48.        Index++;
  49.    }
  50.  
  51.    /** Ahora debería haber números, de lo contrario tenemos un error **/
  52.  
  53.    if (Entrada[Index] < '0' || Entrada[Index] > '9')
  54.    {
  55.        stringstream buffer;
  56.        buffer<<"Error de sintaxis, desconocido elemento: '"<<Entrada[Index]<<"' en la posicion: "<<Index+1;
  57.        throw buffer.str().c_str();
  58.    }
  59.  
  60.    /** Añadimos los enteros **/
  61.  
  62.    while (Entrada[Index] >= '0' && Entrada[Index] <= '9' && Index < Entrada.size())
  63.    {
  64.        Enteros.push_back(Entrada[Index]-48);
  65.        //cout<<Cosa[i]<<endl;
  66.        Index++;
  67.    }
  68.  
  69.    /** Si a continuación encontramos un punto o una coma, esque hay numeros a continuacion **/
  70.  
  71.    if (Entrada[Index] == '.' || Entrada[Index] == ',')
  72.    {
  73.        bool Activado = false;
  74.        Index++;
  75.        while (Entrada[Index] >= '0' && Entrada[Index] <= '9' && Index < Entrada.size())
  76.        {
  77.            Decimales.push_back(Entrada[Index]-48);
  78.            Index++;
  79.            Activado = true;
  80.        }
  81.        if (!Activado)
  82.        {
  83.            throw "Error de sintaxis, se insertó un punto pero no se añadió ningun decimal";
  84.        }
  85.    }
  86.    double Numero = 0; // El valor que devolveremos
  87.    aux = 0;
  88.  
  89.    /** Recorremos los enteros y lo pasamos a número. Como tenemos las cifras simplemente es sumarlas **/
  90.  
  91.    for (auto it = Enteros.begin(); it != Enteros.end(); it++)
  92.    {
  93.        Numero += *it*pow(10,Enteros.size()-aux-1);
  94.        aux++;
  95.    }
  96.    aux = 0;
  97.  
  98.    /** Idem, pero para los decimales **/
  99.  
  100.    if (!Decimales.empty())
  101.        for (auto it = Decimales.begin(); it != Decimales.end(); it++)
  102.        {
  103.            Numero += *it/(pow(10,(aux))*10);
  104.            aux++;
  105.        }
  106.  
  107.    Numero *= signo;
  108.    Index--;
  109.    return Numero;
  110. }
  111.  
  112. int main()
  113. {
  114.        string infix, postfix, token;
  115.        stack <string> standby;
  116.        stack <double> result;
  117.        int i;
  118.        char c;
  119.        double A, B;
  120.  
  121.        /* Cadena de entrada */
  122.        cout << "Intro expresion infija: ">
  123.             getline( cin, infix );
  124.        cout << endl;
  125.  
  126.        /*************************************************************
  127.          PRIMERA PARTE: Procesar la cadena infijo, y crear posfijo
  128.         *************************************************************/
  129.        for ( i = 0; i < infix.size(); i++ )
  130.        {
  131.            /* esto debe cambiar luego a un token o palabra devuelta por
  132.             * el analizador léxico */
  133.            c = infix[i];
  134.            token.clear();
  135.            token += c; /* parece burdo, pero no conozco mejor manera de
  136.     * crear un string a partir de un unico caracter */
  137.  
  138.            /* es un espacio: despreciar */
  139.            if ( c == ' ' ) continue;
  140.  
  141.            cout << "Analizando token: '" << c << "'" << endl;
  142.  
  143.            if ( c >= '0' && c <= '9' )
  144.            {
  145.                cout<<"Init: "<<i<<endl;
  146.                double aux = ConvertirNumero(infix,i);
  147.                cout<<"finit: "<<i<<endl;
  148.                cout << "\tes numero: pasado a posfijo:" << aux<<endl << endl;
  149.                result.push(aux);
  150.  
  151.                // esto es solo para la depuracion
  152.  
  153.                stringstream cosa;
  154.                cosa<<aux;
  155.  
  156.                postfix = postfix + " " + cosa.str();
  157.  
  158.                continue;
  159.            }
  160.  
  161.            /* si se lee un operador: sacar de la pila y pasar al postfijo
  162.             * todos los operadores con una precedencia mayor o igual a la
  163.             * suya, y depositar el mismo en la pila */
  164.            if ( is_operator( token ) )
  165.            {
  166.                cout << "\tes operador:" << endl;
  167.                while ( !standby.empty() && precedence( standby.top() )
  168.                        >= precedence( token ) )
  169.                {
  170.                    cout << "\tpasado operador '" + standby.top() +
  171.                         "' de la pila a posfijo" << endl;
  172.                    postfix = postfix + " " + standby.top();
  173.                    standby.pop();
  174.                }
  175.                standby.push( token );
  176.                cout << "\tcolocar '" << token << "' en la pila" << endl << endl;
  177.                continue;
  178.            }
  179.  
  180.            /* si se lee "(": colocar en la pila */
  181.            if ( token == "(" )
  182.            {
  183.                cout << "pasado a posfijo" << endl << endl;
  184.                standby.push( token );
  185.                continue;
  186.            }
  187.  
  188.            /* si se lee ")": retirar de la pila hasta encontrar '(', y pasar
  189.             * los elementos retirados a posfijo, luego descartar el "(" */
  190.            if ( token == ")" )
  191.            {
  192.                while ( !standby.empty() && standby.top() != "(" )
  193.                {
  194.                    cout << "\tpasado operador '" + standby.top() +
  195.                         "' de la pila a posfijo" << endl << endl;
  196.                    postfix = postfix + " " + standby.top();
  197.                    standby.pop();
  198.                }
  199.                if ( !standby.empty() )
  200.                    standby.pop(); /* descartar el "(" */
  201.            }
  202.        }
  203.  
  204.        /* extraer de la pila cualquier operador restante y pasarlo a la cadena posfijo */
  205.        while ( !standby.empty() )
  206.    {
  207.        cout << "Pasado operador '" + standby.top() +
  208.             "' de la pila a posfijo" << endl << endl;
  209.        postfix = postfix + " " + standby.top();
  210.        standby.pop();
  211.    }
  212.  
  213.    /* Imprimir el posfijo */
  214.    cout << "Posfijo es: \n\t" << postfix << endl << endl;
  215.  
  216.    /****************************************************************
  217.      SEGUNDA PARTE: Procesar la cadena posfijo, y devolver resultado
  218.     ****************************************************************/
  219.  
  220.    A = 0;
  221.    cout << "Evaluando la expresion ..." << endl;
  222.    for ( i = 0; i < postfix.size(); i++ )
  223.    {
  224.  
  225.        c = postfix[i];
  226.        token.clear();
  227.        token += c;
  228.  
  229.        /* si se lee un operando (caracter numerico), depositar en la pila */
  230.        if ( c >= '0' && c <= '9' )
  231.        {
  232.  
  233.  
  234.            continue;
  235.        }
  236.  
  237.        /* si se lee un operador binario, poner en A y B los últimos dos argumentos
  238.         * de la pila y operarlos, guardando el resultado en la pila */
  239.        if ( is_operator( token ) )
  240.        {
  241.            if ( !result.empty() )
  242.            {
  243.                B = result.top();
  244.                result.pop();
  245.            }
  246.            else
  247.            {
  248.                cout << "Argumentos insuficientes para '" << c << "'" << endl;
  249.                return -1;
  250.            }
  251.  
  252.            if ( !result.empty() )
  253.            {
  254.                A = result.top();
  255.                result.pop();
  256.            }
  257.            else
  258.            {
  259.                cout << "Argumentos insuficientes para '" << c << "'" << endl;
  260.                return -1;
  261.            }
  262.  
  263.            cout << "\toperar " << A << token << B << " = ";
  264.            if ( token == "+" )
  265.            {
  266.                A += B;
  267.                result.push( A );
  268.            }
  269.            else if ( token == "-" )
  270.            {
  271.                A -= B;
  272.                result.push( A );
  273.            }
  274.            else if ( token == "*" )
  275.            {
  276.                A *= B;
  277.                result.push( A );
  278.            }
  279.            else if ( token == "/" )
  280.            {
  281.                A /= B;
  282.                result.push( A );
  283.            }
  284.            else if ( token == "%" )
  285.            {
  286.                A = (int )A % (int )B;
  287.                result.push( A );
  288.            }
  289.            else if ( token == "^" )
  290.            {
  291.                A = pow(A, B);
  292.                result.push( A );
  293.            }
  294.            cout << A << endl;
  295.        }
  296.    }
  297.  
  298.  
  299.    if ( !result.empty() )
  300.        cout << endl << "El resultado es: " << result.top() << endl;
  301.  
  302.    return 0;
  303. }
  304.  
  305. /* Verdadero si el token corresponde a un operador. */
  306. bool is_operator( const string token )
  307. {
  308.  
  309.    for ( int i = 0; i < N_operators; i++ )
  310.        if ( operators[i] == token )
  311.            return true;
  312.  
  313.    return false;
  314. }
  315.  
  316. /* Devuelve la precedencia del operador descrito por el
  317.  * string token (-1 si no es un operador) */
  318. int precedence( const string token )
  319. {
  320.  
  321.    for ( int i = 0; i < N_operators; i++ )
  322.        if ( operators[i] == token )
  323.            return precedences[i];
  324.  
  325.    return -1;
  326. }
  327.  

Esto debería funcionarte con número de x cifras y con números decimales/enteros. El separador decimal puede ser ',' o '.' resulta totalmente indiferente.

Por supuesto, hay cosas que se pueden optimizar de ahí. Yo solo te he copypasteado la función y he tocado 1-2 cosas para que funcione (por ejemplo, que el deposito de números en la pila sea en la primera lectura y no en la segunda).

Por cierto:
Código
  1. token.clear();
  2. token += c;

Esto es equivalente a:
Código
  1. token = c;

De todas formas, si solo vas a tener un caracter podrías usar un char a secas :huh:
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #4 en: 23 Marzo 2014, 02:51 am »

Gracias por el token = c !!!

Ahora dos detallitos:

(1) Si podrías hacer el código más portable, que no requiera necesariamente C++11. Yo uso Ubuntu 10.04, de 2010, y g++ no está actualizado a 2011. Tengo problemas con el "auto it", en el otro código tive que cambiar todas las expresiones de ese tipo al tipo "class<T> :: it". Quiero que sea portable porque la idea de ésto es primero usarlo como objeto académico-pedagógico en la Universidad por ejemplo, y no se si todos los estudiantes están actualizado a la última versión del software.

(2) La invocación de la conversión a número empieza cuando se detecta un carácter entre '0' y '9', no con el signo '+' ó '-'. ¿Eso no hará que por ejemplo al recibir 2 * -3, lo interprete como 2 * 3?
En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #5 en: 23 Marzo 2014, 11:25 am »

Gracias por el token = c !!!

Ahora dos detallitos:

(1) Si podrías hacer el código más portable, que no requiera necesariamente C++11. Yo uso Ubuntu 10.04, de 2010, y g++ no está actualizado a 2011. Tengo problemas con el "auto it", en el otro código tive que cambiar todas las expresiones de ese tipo al tipo "class<T> :: it". Quiero que sea portable porque la idea de ésto es primero usarlo como objeto académico-pedagógico en la Universidad por ejemplo, y no se si todos los estudiantes están actualizado a la última versión del software.
No solo necesitas un compilador que soporte C++11 sino que también tienes que activar ese modo en la compilación (creo que era std=C++11 o algo así).

Lo más fácil esque quites los auto y listo. No hay nada más que use de C++11 en ese código.

(2) La invocación de la conversión a número empieza cuando se detecta un carácter entre '0' y '9', no con el signo '+' ó '-'. ¿Eso no hará que por ejemplo al recibir 2 * -3, lo interprete como 2 * 3?
Efective wonder.

Puedes empezar también con un '-', conviertes el número y a falta de operadores asumes una suma.

Por cierto:
Código
  1. const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};

Mucho mejor es lo siguiente:
Código
  1. const char operators[N_operators] = {'+','-','*','/','%','^'};

No me gusta usar strings para cadenas constantes, es un desperdicio de recursos (tanto en espacio como en tiempo).
« Última modificación: 23 Marzo 2014, 13:21 pm por amchacon » En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #6 en: 24 Marzo 2014, 19:40 pm »

Bueno, revisé la función ConvertirNumero(), pero veo que usa objetos complejos como listas. Sin embargo me parece excelente la filosofía usada para reconocer la sintaxis de la cadena, y obtener el número representado. Así que me tomé la libertad de redactarla en un código algo más elemental.

Lo que hago es no formar un conjunto con los dígitos que conforman la parte entera y la parte fraccionaria, sino reconocer los índices inicial y de dichos elementos en la cadena original. Luego voy tomando los dígitos y multiplicándolos por una potencia de 10. Adicionalmente, reemplazar el pow() por una variable base que en cada ciclo se multiplica por 10. Esa era la idea original de la función, creo que se mantiene igual pero ahora compila más rápido porque no necesita enlazar con bibliotecas de clases, jeje.
Código
  1. double str_to_dbl( const char *s, int *index_ptr ) {
  2.  
  3.   char c;
  4.   int i;
  5.   int int_start, int_end; /* indices de inicio y fin de parte entera */
  6.   int frac_start,frac_end; /* indices de inicio y fin de parte fraccionaria */
  7.   char sign = 0; /* flag de signo, 1 para negativo */
  8.   double number, base;
  9.  
  10.   /* descartamos espacios en blanco iniciales */
  11.   i = 0;
  12.   while ( s[i] == ' ' )
  13.      i++;
  14.  
  15.   /* reconocemos el carácter de signo (opcional) */
  16.   if ( ( c = s[i] ) == '+' || c == '-' ) {
  17.      if ( c == '-' ) sign = 1;
  18.      i++;
  19.   }
  20.  
  21.   /* reconocemos la parte entera, si la hay */
  22.   int_start = -1;
  23.   while ( ( c = s[i] ) >= '0' && c <= '9' ) {
  24.      if ( int_start == -1 ) int_start = i;
  25.      i++;
  26.   }
  27.   if ( int_start != -1 )
  28.      int_end = i - 1;
  29.  
  30.   /* caracter de punto decimal */
  31.   if ( s[i] == '.' ) {
  32.  
  33.      i++;
  34.      /* reconocemos la parte decimal, si la hay */
  35.      frac_start = -1;
  36.      while ( ( c = s[i] ) >= '0' && c <= '9' ) {
  37.         if ( frac_start == -1 ) frac_start = i;
  38.         i++;
  39.      }
  40.      if ( frac_start != -1 )
  41.         frac_end = i - 1;
  42.   }
  43.  
  44.   /* calcular el número */
  45.   number = 0;
  46.   if ( int_start != -1 ) {
  47.      base = 1;
  48.      while ( int_end >= int_start ) {
  49.         number += (s[int_end] - '0') * base;
  50.         int_end--;
  51.         base *= 10;
  52.      }
  53.   }
  54.   if ( frac_start != -1 ) {
  55.      base = 10;
  56.      while ( frac_start <= frac_end ) {
  57.         number += (s[frac_start] - '0') / base;
  58.         frac_start++;
  59.         base *= 10;
  60.      }
  61.   }
  62.   if ( sign ) number *= -1;
  63.  
  64.   if ( int_start != -1 || frac_start != -1 )
  65.      *index_ptr = i;
  66.   else
  67.      *index_ptr = -1;
  68.  
  69.   return number;
  70. }

Un pequeño detalle en la función ConvertirNumero es que arrojaba error si el número carecía de parte entera, e.g. -.35. Esto se corrige disponiendo que tanto la parte entera como la decimal sean opcionales, pero deba estar presente una de las dos:
Código
  1. if ( int_start != -1 || frac_start != -1 )
  2.   /* ... */

¿Pero sabes qué? Desempolvando los papeles veo que la función de biblioteca strtod(const char *s, char **endptr) ya nos hace este trabajo, y además actualiza endptr al primer caracter de la cadena no reconocible como parte de un número, y si coincide con el primero de la cadena significa que no se pudo reconocer ningún número. Es de biblioteca, es estándar y sobre todo, ya está hecha, jajaja.

Sin embargo, habría una razón para que nuestras funciones pudieran preferibles a strtod(): que podrían avisar sobre error de sintaxis. Pero para que las mismas puedan competir contra la función de biblioteca les hace falta que reconozcan números en formato de notación exponencial o científica.
En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #7 en: 24 Marzo 2014, 22:10 pm »

Hehe. Ya te dije que mi función era una chapuzilla ^^

Yo ahora lo haría con el objeto stringstream:
Código
  1. if ( c >= '0' && c <= '9' )
  2. {
  3.   double aux;
  4.  
  5.   stringstream cosa(infix.substr(i)); // crea un substring a partir de la posicion i
  6.   cosa >> aux;
  7.  
  8.   result.push(aux);
  9.  
  10.   continue;
  11. }
  12.  

De hecho podría ir sacando todos los números de ese modo:

Código
  1. cout << "Intro expresion infija: ">
  2. getline( cin, infix );
  3. cout << endl;
  4.  
  5. stringstream cosa(infix);
  6. double aux;
  7.  
  8. cosa>>aux;
  9.  
  10. do
  11. {
  12.    result.push(aux);
  13.    cosa>>aux;
  14. }while (cosa.good());
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #8 en: 25 Marzo 2014, 19:21 pm »

Por cierto, y un comentario fuera de lugar, ¿por qué no compartes en el foro algún algoritmo de esteganografía de ficheros elaborado en/para C? Con teoría básica de cómo funciona, etc.

¿o ya lo has hecho?
En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Proyecto calculadora: Convertir infijo a posfijo.
« Respuesta #9 en: 25 Marzo 2014, 22:34 pm »

¿Estenografía en ficheros? ¿Dependerá del formato del fichero en cuestión no? La idea es buscar los fallos del formato en cuestión.

El de archivos rar es una implementación en C++ de esta técnica:
http://neobits.net/NeobitsOrg/560.html
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
convertir proyecto activex de C++ a vb
Programación Visual Basic
el_c0c0 0 1,373 Último mensaje 1 Marzo 2009, 22:04 pm
por el_c0c0
Prefijo – Postfijo – Infijo (C#)
.NET (C#, VB.NET, ASP)
ahome31 0 5,588 Último mensaje 2 Noviembre 2009, 06:37 am
por ahome31
Convertir Proyecto Windows Forms a Web
.NET (C#, VB.NET, ASP)
seba123neo 4 12,662 Último mensaje 9 Noviembre 2011, 01:51 am
por seba123neo
convertir un proyecto en Opensource?
GNU/Linux
Kase 0 1,117 Último mensaje 27 Marzo 2012, 09:36 am
por Kase
La calculadora de Windows es el proyecto más popular de todo GitHub desde ....
Noticias
wolfbcn 0 488 Último mensaje 21 Marzo 2019, 02:15 am
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines