Al escribir código, a veces encontramos situaciones en las que necesitamos analizar las cuatro expresiones aritméticas por nosotros mismos. Este artículo presenta brevemente el uso de JavaScript para implementar el análisis de cuatro expresiones aritméticas simples.
1. Familiarizado con el concepto
La notación Infix (o notación Infix) es un método general de representación de fórmula aritmética o lógica. El operador está en el medio del operando en forma de infijo (ejemplo: 3 + 4). Es decir, utilizamos las expresiones aritméticas más utilizadas. Las expresiones infix son más fáciles de entender para los humanos, pero no son fáciles para el análisis de la computadora.
La notación de polaco inverso (RPN, o notación polaca inversa) es un método de expresión matemática introducido por el matemático polaco Jan Vukasevich en 1920. En la notación inversa polaca, todos los operadores se colocan detrás del operando, por lo que también se llama notación sufijo. La notación inversa del polaco no requiere soportes para identificar la prioridad del operador. La notación inversa del polaco es fácil de usar una estructura de pila para analizar y calcular la expresión, por lo que aquí analizamos las cuatro expresiones de elementos, que primero se convierte de la expresión infijo a la expresión inversa del polaco. Luego calcule el valor.
2. Proceso de conversión
Convierta una expresión infijo a una expresión de sufijo (algoritmo de campo de programación)
1. Entra en la cola y aparece una marca
2. Si la marca es un número, agrégalo a la cola de salida
3. Si es un operador (+-*/), compárelo con el operador en la parte superior de la pila en la pila de salida. Si la prioridad es menor o igual al operador en la parte superior de la pila, aparezca el operador en la parte superior de la pila y agréguela a la cola de salida (bucle hasta que no se cumplan las condiciones anteriores) y finalmente empuje el operador a la pila.
4. Si es un soporte izquierdo, empújalo en la pila
5. Si es un soporte cercano, el operador se sale constantemente de la pila y se agrega a la cola de salida, y sabe que el elemento en la parte superior de la pila es el soporte izquierdo. El soporte izquierdo aparece y no agrega la cola de salida. Si no se encuentra un soporte izquierdo, significa que los soportes en la expresión original son asimétricos y hay un error.
6. Si la cola de entrada está vacía y todavía hay operadores en la pila, si el operador en la parte superior de la pila está del soporte izquierdo, significa que la expresión original tiene soportes no coincidentes. Explique los operadores en la pila uno por uno y agréguelos a la cola de salida.
7. Completado
3. Convertir la implementación del código
función isoperator (valor) {var operatorstring = "+-*/()"; return operatorstring.indexof (valor)> -1} function getPrioraty (valor) {switch (valor) {case '+': case '-': return 1; case '*': '/': return 2; predeterminado: 0;}} function priority (O1, o2) getPrioraty (o2);} function dal2rpn (exp) {var inputStack = []; var outputStack = []; var outputqueue = []; for (var i = 0, len = exp.length; i <Len; i ++) {var Cur = exp [i]; if (cur! = '') {inputStack.push (cur);}} while (inputStack.length> 0) {var cur = inputStack.shift (); if (isoperator (cur)) {if (cur == '(') {outputStack.push (cur);} else if (cur == ')') {var po = outputStack.pop (); while (po! = '(' && outputStack.length> 0) {outputQueue.push (po); po = outputStack.pop ();} if (po! = '(') {throw "Error: Unmatched ()";}} else {while (prioraty (cur, outputStack [outputStack.length - 1]) && salida 0) {outputQueue.push (outputStack.pop ());} outputStack.push (cur);}} else {outputqueue.push (nuevo número (cur));}} console.log ('step dos'); if (outputintack> 0) {if (outputStack [outputStack. == '(') {Throw "Error: Unmatched ()";} while (outputStack.length> 0) {outputQueue.push (outputStack.pop ());}} console.log ('step tres'); return outputqueue;} console.log (dal2rpn ('1 + 2'); console.log (dal2rpn (»1 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + mil 3 ')); console.log (dal2rpn (' 1 + 2 * 3 ')); console.log (dal2rpn (' 1 + 2 * 3 - 4 /5 ')); console.log (dal2rpn (' (1 + 2) '); console.log (dal2rpn (' (1 + 2) * (3 - 4) 5 ')); console.log (dal2rpn (' (1 + 2) * ((3 - 4) / 5) '));4. Evaluación de expresión polaca inversa
1. Aparece una marca de la cola de entrada
2. Si es un operando, agrégalo a la pila de salida
3. Si es un operador, establezca dos operandos desde la pila de salida y calcule, y presione el valor calculado en la pila de salida.
4. Operación de bucle. Si la cola de entrada está vacía y solo hay un número en la pila de salida, este número es el resultado, de lo contrario habrá un operando innecesario.
5. Calcule el código
función evalrpn (rpnqueue) {var outputStack = []; while (rpnqueue.length> 0) {var cur = rpnqueue.shift (); if (! isoperator (cur)) {outputStack.push (cur);} el más {if (outputaltack.length <2) {throw "stack longitud";} vAR = outyAd; = outputStack.pop (); outputStack.push (getResult (fir, sec, cur));}} if (outputStack.length! = 1) {throw "no válido expresión";} else {return outputStack [0];}}6. Conclusión
La representación inversa de polaco no se usa cuando entra en contacto por primera vez con ella, pero después de familiarizarse con ella, encontrará que la idea es realmente muy simple, a diferencia de la representación infix, que tiene varias prioridades, y hay soportes, que son una lógica particularmente problemática. La representación inversa del polaco es relativamente concisa, y no hay necesidad de considerar la prioridad, y no hay necesidad de usar soportes, soportes y aparatos ortopédicos para interrumpir la situación.