¡Solicitud urgente! Hecho usando pila de estructura de datos
2 Cálculo de expresiones
2.1 Análisis de prioridad del operador
El análisis de prioridad del operador define una determinada relación de prioridad entre operadores, que se pueden expresar en las siguientes tres relaciones:
a < ba es menor que b
a = ba es igual a b
a > ba es mayor que b
Donde a y b representan una prioridad. p> donde a y b representan un operador. A diferencia de mayor que, igual y menor que en matemáticas, a < b no significa b > a, y a = b no significa b = a.
2.2 Representación de expresiones
Dentro de la máquina, cualquier expresión consta de operandos, operadores y delimitadores (que indican el final de la expresión). Supongamos que los operadores analizados aquí solo incluyen los cuatro operadores aritméticos de suma, resta, multiplicación y división, así como los paréntesis izquierdo y derecho. Por ejemplo, la expresión aritmética A (B - C/D) * E. Los operadores en esta expresión aritmética generalmente siempre aparecen entre los dos operandos, que se denominan expresiones intermedias. En el sistema de compilación de la computadora, antes de procesar una expresión de prefijo, siempre se convierte en una expresión de posfijo, es decir, el operador de la expresión aparece después de los operandos y no contiene paréntesis. Al convertir una expresión infija en una expresión postfija correspondiente, primero se deben considerar las reglas de las operaciones aritméticas. Las reglas de las operaciones aritméticas son (1) primero multiplicar y dividir, luego suma y resta; (2) primero dentro de los corchetes, luego fuera de los corchetes (3) cuando están en el mismo nivel, primero a la izquierda y luego a la derecha; La expresión postfija anterior se puede escribir como ABCD/-E*, lo que muestra que la expresión postfija tiene dos características: (1) El orden de los operandos de la expresión postfija es el mismo que el de la expresión postfija, pero el orden de Los operadores han cambiado. El orden de los operadores de una expresión postfija es su orden de ejecución; (2) Las expresiones postfija no tienen paréntesis (como se muestra en la Tabla 1).
Tabla 1 Métodos de procesamiento de expresiones postfijas
2.3 Relación de precedencia de operadores
De las características (1) de las expresiones postfijas, se puede ver que el orden de operadores es el mismo que el de las expresiones infijas, excepto que el orden de los operadores cambia. El sistema de compilación escanea la expresión postfix de izquierda a derecha y cada vez que se lee un operando, se genera como parte de la expresión postfix. El sistema creará una pila para almacenar operadores. Inicialmente habrá un separador # en la parte superior de la pila, que también se considera un operador. Cada vez que se lee un operador, el sistema compara su prioridad con la prioridad del operador en la parte superior de la pila para decidir si colocar el operador de lectura en la pila o usar el operador superior como parte de la expresión postfija de la salida. La Tabla 2 enumera la relación de precedencia entre los operadores aritméticos, incluidos los cuatro operadores aritméticos de suma, resta, multiplicación y división, así como los corchetes y delimitadores izquierdo y derecho. θ1 en la tabla representa el operador en la parte superior de la pila y θ2 representa el operador leído por el escaneo actual.
Tabla 2 Relaciones de precedencia de operadores
La Tabla 2 muestra variaciones de las tres reglas para operaciones cuadráticas.
Para la regla (1), cuando θ1 es o - y θ2 es * o /, la prioridad de θ1 es menor que la de θ2 (multiplicación y división primero, luego suma y resta para la regla (2), cuando θ1 es, -, * o /, cuando θ2 es (, la prioridad de θ1 es menor que la prioridad de θ2 (primero los paréntesis, luego los corchetes); y cuando θ1 es, -, * o /, θ2 es), la prioridad de θ1 es mayor que la prioridad del nivel θ2 (resuelva primero el valor entre paréntesis para la regla (3), cuando la prioridad del operador de θ1 y el operador de θ2 son las mismas, haga que θ1 tenga una prioridad más alta (primero la izquierda y luego la derecha); cuando la prioridad es la misma). Dado que la expresión sufijo no tiene paréntesis, cuando θ1 es (, θ2 es), el símbolo "=" se usa para indicar que se elimina un par de paréntesis. Cuando θ1 es # y θ2 también es #, significa que se procesa toda la expresión. Los espacios en la Tabla 2 indican que esta situación no está permitida. Una vez que ocurre, es un error de sintaxis en la expresión intermedia.
2.4 Cálculo de expresión
Después de convertir la expresión postfija en la expresión postfija correspondiente, el método para calcular el valor de la expresión de acuerdo con la expresión postfija es el siguiente: Configure un valor lo suficientemente grande pila, una vez Después de llegar, la expresión del sufijo se escanea en secuencia. Cada vez que se lee un operando, se empuja a la pila. Cada vez que se lee un operando, se sacan dos operandos de la parte superior de la pila, la operación representada. por los operandos y el resultado de la operación se utiliza como operando. Cada vez que se lee un operando, se toman dos operandos de la parte superior de la pila, se realiza la operación representada por los operandos y el resultado del cálculo se inserta en la pila como un nuevo operando. Esto se repite hasta que se lee la expresión de sufijo. . El último operando en la parte superior de la pila es el resultado de la expresión aritmética.
3 Implementación del algoritmo
#include
char newstr[20]; int p=0
char proceder(char x1, char x2) /* Comparación aritmética*/
{char resultado1;
char Midstring[2]
resultado1='lt;'; ]=x2; Midstring[1]='\0';
if (((x1==' '||x1=='-')amp; amp; strstr(" -)#" , Cadena media)! =-1)
||((x1=='*'||x1=='/')amp;amp;strstr(" -*/)#",Cuerda media) ! =-1)
||(x1==')'amp;amp;strstr(" -*/)#",Midstring)! =-1))
result1='gt;';
else if((x1=='(' amp;amp;x2==')')||( x1=='#' amp; x2=='#'))
resultado1='='
else if(( x1=='(' amp; amplificador x2=='#')||(x1==')' amplificador x2=='(')||(x1=='#' amplificador; x2==')'))
resultado1=' ';
return(resultado1);}
int str.
int strstr(char str1[], char str2[])
{int i, j, k, m, n;
char tempStr1, tempStr2
m=strlen(str1);
n=strlen(str2);
for(i=0;i {k=i;
for(j=0;jlt;1; j , k )
{tempStr1=str1[k];
tempStr2=str2[j]
if(tempStr1==tempStr2)
Continuar;
De lo contrario, desconectar;
if(tempStr1==tempStr2)
Continuar
De lo contrario, desconectar abierto.
if(jgt;=n) return(1);}
return(-1);}
/* Convertir expresión de sufijo a través de expresión intermedia Fórmula */
intprotfix(char str[])
{char stack[20];
char x1, x2, x
; p>int j=0, k=0;
pila[0]='#';
x2=str[j]; > x1=pila[0];
mientras(1) < noticiastr[p ]=x2
j ; > else
else.
else
Texto original de este artículo
if(proceed(x1,x2)==' lt ;')
{pila[ k]=x2;
x1=pila[ k]
x2=cadena[j]; p>
}else if(proceed(x1, x2)=='gt;')
{ x=stack[k--]
newstr[p ] =x;
x1=pila[k]; }
else if(proceder(x1, x2)=='='amp;amp;x1=='(' amp ; amplificador; amplificador; x2==')')
{k--; x1=pila[k]; p>
De lo contrario
if( proceder(x1, x2)=='='amp;amp;x1=='#'amp;amp;x2=='#') p >
return(1);
else if(proceed(x1, x2)==' ')
break;}
return( 0 );}
double count(char str[])/* Calcular el valor de la expresión*/
{double x1, x2, x; int a, i=0;
while(str[i]!= '\0')
{if(isdigit(str[i]))
push(str[i ]-48);
else
Cambiar(str[i])
{ case ' ': x1=pop(); ;
x = x1 x2; push(x);
caso '-': x1=pop(); > x=x1-x2; empujar(x); romper
caso '*': x1=pop(); ; empujar(x); romper;
caso '/': x1=pop(); x2=pop(); romper; }
i;}}
return(x);}
4 Conclusión
Como base del lenguaje de programación, el cálculo de expresiones es un conocimiento básico necesario para los programadores y estudiantes avanzados de lenguajes de programación. Este artículo brinda el proceso de cálculo de expresiones aritméticas a través del análisis de prioridad aritmética y métodos de pila, y brinda una descripción del algoritmo, que puede ayudar a los principiantes en lenguajes avanzados y a los programadores de computadoras a familiarizarse con el proceso de procesamiento de cálculo de expresiones internas de la computadora y comprender mejor Aprenda y domine Técnicas de programación en lenguajes de alto nivel.