Evaluación basada en pila de expresiones aritméticas infijas
La evaluación de expresiones aritméticas infijas basadas en pila es un problema algorítmico común. La expresión infija es una expresión matemática común, como 3 4*2/(1-5). En este problema, necesitamos usar la pila para resolver el valor de la expresión.
Necesitamos conocer las reglas gramaticales de la expresión infija. Las expresiones infijas constan de operandos (números, letras, etc.). ) y operadores (suma, resta, multiplicación, división, etc.) La precedencia de los operadores está determinada por paréntesis y reglas matemáticas. Por ejemplo, la multiplicación y la división tienen prioridad sobre la suma y la resta.
La solución basada en pila es: crear una pila vacía para almacenar operandos y operadores; escanear la expresión infija de izquierda a derecha si el carácter actual es un operando, presionarlo Apilar; un operador, el operador se saca de la parte superior de la pila y se compara la prioridad si la prioridad del operador actual es mayor que la del operador en la parte superior de la pila, el operador actual se empuja a la pila;
De lo contrario, el operador superior se extrae de la pila, la expresión se evalúa y el resultado se envía; si se encuentra un paréntesis izquierdo, se empuja a la pila; se extrae el operador de la pila, se calcula la expresión y se coloca el resultado en la pila; se repiten los pasos 3 a 6 hasta que se escanea la expresión completa en la parte superior de la pila, se extrae y se devuelve;
Características de las expresiones infijas:
1. Uso de paréntesis: Las expresiones infijas utilizan paréntesis para aclarar la prioridad. Por ejemplo, en la expresión 3 4*2, la multiplicación tiene mayor prioridad que la suma, por lo que se necesitan paréntesis para garantizar que la multiplicación se ejecute primero.
2. Prioridad del operador: los operadores en expresiones infijas tienen prioridad y los operadores con mayor prioridad se operan antes que los operadores con menor prioridad. Por ejemplo, la multiplicación y la división tienen prioridad sobre la suma y la resta.
3. El orden de los operandos: Los operandos en expresiones infijas se calculan de izquierda a derecha. Por ejemplo, en la expresión 3 4*2, primero se calcula el resultado de 4*2 y luego el resultado se suma a 3.
4. Alta legibilidad: la expresión infija es una expresión matemática intuitiva que es fácil de leer y comprender. Las expresiones infijas no son la única forma de expresar expresiones matemáticas. Existen otras notaciones, como expresiones de prefijo y expresiones de sufijo. La expresión de prefijo escribe el operador antes del operando y la expresión de posfijo escribe el operador después del operando.