(edición posterior)
Acabo de terminar esta tarea. Estaba limitado a usar System y System.collections.Generic. Nada más. Terminé usando una List<> de from the collections.Generic. y los principios de la notación polaca. Después de cada "Encuentro" de un signo de operación (+-/*) usé el índice - 1 y - 2 para obtener los 2 números anteriores y realizar la operación. Luego usé .Insert para insertar el resultado en el índice actual, luego usé .Remove para restar de la lista los números y el operador que acabo de usar y luego continué con la función recursiva en la nueva lista obtenida a partir del índice de 0 otra vez. Los artículos de notación polaca publicados en los comentarios me ayudaron más a comprender la lógica detrás de esto.
*
Estoy tratando de descubrir en los últimos días una forma de implementar la siguiente lógica en el programa ac#. Usando solo System.
Esta es una calculadora de consola pequeña donde la entrada se inserta en una sola línea en la consola. Por ejemplo, la siguiente entrada + / * + 65 32 46 2 - 1 1.25 debería traducirse en una operación matemática parecida a esta => ((65 + 32) * 46) / 2 + (1 - 1.25)
Otro ejemplo sería * + 3 2 - 9.5 6.5 : esto debe calcularse en el siguiente orden 3 + 2 * (9.5 - 6.5) .
Otro ejemplo / + 5 3 2 es igual a => (5 + 3) / 2
Tengo que hacer la función recursiva.
Descubrí cómo hacerlo si todas las operaciones cantan delante de los dígitos en la entrada. (Solo separo la lista de operadores y la invierto y obtengo dos listas separadas: una que contiene los signos de operación y la otra que contiene los números). Lo que estoy luchando es encontrar una manera de hacer las operaciones si hay un signo matemático entre los números (como en el primer y segundo ejemplo).
No necesariamente necesito un código para esto, tal vez una explicación o si alguien pudiera indicarme la dirección correcta donde puedo leer sobre algún algoritmo/fórmula matemática o algo que pueda ayudarme a comprender mejor cómo implementar esto.
Gracias de antemano.
El método normal de evaluar expresiones de notación polaca no requiere recursividad, usa una pila (como Forth o RPN) y evalúa sobre la marcha.
Una manera fácil de crear una versión recursiva es considerar el lenguaje de expresión BNF y luego crear un analizador descendente recursivo a partir de la gramática.
Por ejemplo, un posible BNF sería:
expr = op arg arg op = [+-*/] // cheating; use regex to describe terminal arg = number | expr number = [0-9]+ // using Regex to describe terminalAsí que ahora crearías métodos para cada elemento:
double expr() { string opStr = op(); double arg1 = arg(); double arg2 = arg(); double ans; switch (opStr) { case "+": ans = arg1+arg2; break; // case and so on } return ans; } static string operators = "+-*/"; string op() { if (operators.Contains(peekChar())) return nextCharAsStr(); else throw new Exception("Missing operator"); } double arg() { double? num = number(); if (num.HasValue) return num.Value; else return expr(); } double? number() { string ans = ""; while (Char.IsDigit(peekChar())) ans += nextCharAsStr(); if (String.IsNullOrEmpty(ans)) return null; else return Double.Parse(ans); }NOTA: Los espacios en blanco y el final de la cadena se dejan como ejercicio para el lector.
También podría usar un tokenizador que extraiga terminales de la cadena en lugar de trabajar directamente con caracteres en los métodos de terminal del analizador.
Hay diferentes tipos de recursividad. El más común (recurrencia de código) es probablemente lo que está preguntando, en el que una función (o un conjunto de funciones) se llaman entre sí hasta que se alcanza algún tipo de condición de salida.
Para esto, optaría por un enfoque más recursivo de datos. Esta versión solo admite operandos de un solo dígito y operadores binarios.
(Pseudocódigo realmente malo a continuación).
stack<char> operators; stack<char> operands; for(var i=input.Length-1; i>=0; --i) { var c = input[i]; if (Char.IsDigit(c)) /// note that this only handles single-digit numbers. operands.push(c); else operators.push(c); if (operators.count >= 1 && operands.count >= 2) { var operator = operators.pop(); /// handle binary operators left = operands.pop(); right = operands.pop(); switch(operator) { case '+' : result = left + right; break; case '-' : result = left - right; break; case '*' : result = left * right; break; case '/' : result = left / right; break; } operands.push(result); } } var result = operands.pop(); Cuando eso se complete, su pila de operands debería tener solo un elemento que sea el resultado de la expresión. y operators deben estar vacíos. Si tiene operadores sobrantes, entonces no hubo suficientes valores en la entrada. Si tiene más de un valor en los operandos, no había suficientes operadores en la entrada. Si tiene cero operandos (es decir, ningún resultado), entonces no había ninguno en la entrada para empezar.
Para una implementación real, querrá analizar la cadena para obtener operandos de varios dígitos, manejar operadores unarios, ignorar espacios en blanco, etc.
Editar: invirtió la dirección del bucle.