Examen de ingreso de posgrado de 2015: ¿Algoritmos de uso común para estructuras de datos informáticos (3)?

Por ejemplo: Exp=a*b (c-d/e)*f

Si Exp=a*b (c-d/e)*f, entonces es

p>

El tipo de prefijo es: *ab*-c/def.

La fórmula infija es: a * b c-d/e * f.

El sufijo es ab*cde/-fx

Una comparación exhaustiva de sus relaciones puede sacar las siguientes conclusiones:

1. la tercera fórmula El orden relativo de los números es el mismo";

(Entre los tres órdenes de acceso de los árboles binarios, el orden de acceso relativo de las hojas es el mismo)

2. " Operaciones" en las tres expresiones El orden relativo entre símbolos es diferente";

3. Infix pierde información entre corchetes, lo que hace que el orden de las operaciones sea incierto;

(Las operaciones de prefijo y postfijo solo requieren una pila para almacenar los operandos, la evaluación infija requiere dos pilas, pila de símbolos y operación

Hacer una pila)

4. operandos consecutivos. Los operadores delante de ellos y cerca de ellos forman una expresión mínima;

5. Las reglas de operación de los tipos de sufijo son:

El orden en que aparecen los operadores ampmiddot. la fórmula es exactamente la expresión El orden de las operaciones de la expresión;

Cada operador de ampmiddot y los dos operandos que aparecen antes y cerca de él forman una expresión mínima;

6. Reglas aritméticas:

Si es un operando, se coloca directamente en la pila.

Si es un operador. Esto se compara con la parte superior actual de la pila. Si es más alto que la parte superior actual de la pila, colóquelo en la pila. Si es bajo, significa que la parte superior actual de la pila es la más alta y debe calcularse primero. Según el principio de compilación, la parte superior actual de la pila ya es la frase principal más a la izquierda)

De hecho, el proceso de evaluación directa de expresiones infijas y el proceso de conversión de expresiones infijas en expresiones postfijas son sorprendentemente similares. , Excepto que la evaluación directa Evaluación es para encontrar y la conversión a sufijo es para salida.

Algoritmo de evaluación directa para expresiones infijas:

OPNDType EvalueExpression()

{//OPTR y OPND son la pila de operadores y la pila de operandos respectivamente.

pila de inicio(OPTR); Push(OPTR, ' # ');

pila de inicio(OPND); c = getchar(); c! ='#'|| GetTop(OPTR)! ='#')

{

If (!IN(c, OP)) //Si es el operando , Vaya directamente a la pila de operandos.

{ push(OPND, c);

c = getchar();

}

Else //Si es un operador, luego compárelo con la parte superior actual de la pila.

{

cambiar(precend(GetTop(OPTR), c))

{

Caso 'lt': push( OPTR , c); // Más alto que la parte superior actual de la pila colocada en la pila.

c = getchar();

Break;

Case '= ': Pop(OPTR, x); //En la tabla de prioridades que diseñamos,

c = getchar(); //Solo "(" y ")" son iguales.

Break; //Solo hay '(' ')' en el medio de la especificación.

//Entonces podemos simplemente hacer estallar '('.

Case ">": //Si es más bajo que la parte superior actual de la pila, la parte superior de la pila debería calcularse primero (especificado primero).

pop(OPTR, theta); //Extrae el operador superior de la pila.

Pop(OPND, b); //Obtiene el operando, que es el operando anterior.

Pop(OPND, a); //En la parte inferior (primero en entrar, último en salir de la pila)

Push(OPND, Operate(a, theta, b)); //Operación El resultado se coloca en la pila.

//(Es el operando de otros operadores)

Romper

}//Cambiar

}//De lo contrario <; /p>

}//whild

Return GetTop(OPND); //Lo último que queda en la pila de operandos es el resultado de la expresión completa.

}

Algoritmo de expresión infija a expresión postfija

Voidtrans-post (char e [n], char b [n]) // Conversión de intermedio y expresiones postfix //

{//E[n] es la expresión infija y B[n] es el espacio de almacenamiento de la expresión postfix.

int i=0,j=0; char x; stype S;

Clearstack push(S, '#'); //'#' en la pila //

Do {

x = E[i]; //Escanea los componentes de la expresión actual //

if(x = ' # ') // en sufijo el final de la expresión.

Y (!empty stack))//Entre todas las pilas, # y # tienen la prioridad más baja.

b[j]= = pop(S); //Por lo tanto, se deben especificar todas las operaciones de la pila actual.

//Muestre el operador en la parte superior de la pila y expanda la pila hasta #//

else if (isdigit(x))

b[ j ]= x; //El operando se genera directamente //

Elseif (x =')')//meet) entonces debes encontrar (

{

while (Getstop(S)!='(')

b[j ]= pop(S); //Imprime la parte superior de la pila y expándela //

Música pop; //Return "(" //

}

Else //x es un operador //

{

While (preempted (get stop(s), x))//Compara la parte superior de la pila (q1) y x//

b[j]= pop(S //q); 1 gt;=x, genera el símbolo superior de la pila y lo empuja hacia atrás a la pila //

Push(S, x); //q 1 lt; /

}

} mientras (x!='#');

b[j]= ' # ';

}//Establezca el terminador de expresión//

Si tiene preguntas sobre el examen de ingreso de posgrado, no sabe cómo resumir el contenido del centro de examen de ingreso de posgrado o no conoce las políticas locales. para registrarse para el examen de ingreso de posgrado, haga clic en la parte inferior para consultar el sitio web oficial y obtener materiales de revisión gratuitos: /xl/