Dada una expresión como una string str que consta de números y operadores aritméticos básicos (+, -, *, /), la tarea es resolver la expresión. Tenga en cuenta que los números utilizados en este programa son números de un solo dígito y no se permiten paréntesis.
Ejemplos:
Entrada: str = “3/3+4*6-9”
Salida: 16
Dado que (3/3) = 1 y (4 * 6) = 24.
Entonces la expresión general se convierte en (1 + 24 – 9) = 16
Entrada : string = “9*5-4*5+9”
Salida: 16
Enfoque: se crea una clase Stack para almacenar números y operadores (ambos como caracteres). La pila es un mecanismo de almacenamiento útil porque, al analizar expresiones, es necesario acceder con frecuencia al último elemento almacenado; y una pila es un contenedor de último en entrar, primero en salir (LIFO).
Además de la clase Stack, también se crea una clase llamada express (abreviatura de expresión), que representa una expresión aritmética completa. Las funciones miembro de esta clase permiten al usuario inicializar un objeto con una expresión en forma de string, analizar la expresión y devolver el valor aritmético resultante.
Así es como se analiza una expresión aritmética.
un punterose inicia a la izquierda y se itera para observar cada carácter. Puede ser un número (siempre un carácter de un solo dígito entre 0 y 9) o un operador (los caracteres +, -, * y /).
Si el carácter es un número, se coloca en la pila. El primer operador encontrado también se empuja a la pila. El truco es que se manejan los operadores posteriores. Tenga en cuenta que el operador actual no se puede ejecutar porque el número que le sigue aún no se ha leído. Encontrar un operador es simplemente la señal de que podemos ejecutar el operador anterior, que se almacena en la pila. Es decir, si la secuencia 2+3 está en la pila, esperamos a encontrar otro operador antes de realizar la suma.
Así, siempre que el carácter actual sea un operador (excepto el primero), el número anterior (3 en el ejemplo anterior) y el operador anterior (+) se sacan de la pila, colocándolos en las variables lastval y lasttop. Finalmente, se saca el primer número (2) y se realiza la operación aritmética sobre los dos números (obteniendo 5).
Sin embargo, cuando se encuentran * y / que tienen mayor precedencia que + y –, la expresión no se puede ejecutar. En la expresión 3+4/2, el + no se puede ejecutar hasta que se realice la división. Entonces, el 2 y el + se vuelven a poner en la pila hasta que se realiza la división.
Por otro lado, si el operador actual es un + o -, se puede ejecutar el operador anterior. Es entonces cuando se encuentra el + en la expresión 4-5+6, está bien ejecutar el -, y cuando se encuentra el – en 6/2-3, está bien hacer la división. La tabla 10.1 muestra las cuatro posibilidades.
| Operador anterior | Operador actual | Ejemplo | Acción |
|---|---|---|---|
| + o – | * o / | 3+4/ | Empuje el operador anterior y el número anterior (+, 4) |
| * o / | * o / | 9/3* | Ejecutar operador anterior, empujar resultado (3) |
| + o – | + o – | 6+3+ | Ejecutar operador anterior, empujar resultado (9) |
| * o / | + o – | 8/2- | Ejecutar operador anterior, empujar resultado (4) |
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <cstring>
#include <iostream>
using namespace std;
// Length of expressions in characters
const int LEN = 80;
// Size of the stack
const int MAX = 40;
class Stack {
private:
// Stack: array of characters
char st[MAX];
// Number at top of the stack
int top;
public:
Stack()
{
top = 0;
}
// Function to put a character in stack
void push(char var)
{
st[++top] = var;
}
// Function to return a character off stack
char pop()
{
return st[top--];
}
// Function to get the top of the stack
int gettop()
{
return top;
}
};
// Expression class
class Express {
private:
// Stack for analysis
Stack s;
// Pointer to input string
char* pStr;
// Length of the input string
int len;
public:
Express(char* ptr)
{
pStr = ptr;
len = strlen(pStr);
}
// Parse the input string
void parse();
// Evaluate the stack
int solve();
};
void Express::parse()
{
// Character from the input string
char ch;
// Last value
char lastval;
// Last operator
char lastop;
// For each input character
for (int j = 0; j < len; j++) {
ch = pStr[j];
// If it's a digit then save
// the numerical value
if (ch >= '0' && ch <= '9')
s.push(ch - '0');
// If it's an operator
else if (ch == '+' || ch == '-'
|| ch == '*' || ch == '/') {
// If it is the first operator
// then put it in the stack
if (s.gettop() == 1)
s.push(ch);
// Not the first operator
else {
lastval = s.pop();
lastop = s.pop();
// If it is either '*' or '/' and the
// last operator was either '+' or '-'
if ((ch == '*' || ch == '/')
&& (lastop == '+' || lastop == '-')) {
// Restore the last two pops
s.push(lastop);
s.push(lastval);
}
// In all the other cases
else {
// Perform the last operation
switch (lastop) {
// Push the result in the stack
case '+':
s.push(s.pop() + lastval);
break;
case '-':
s.push(s.pop() - lastval);
break;
case '*':
s.push(s.pop() * lastval);
break;
case '/':
s.push(s.pop() / lastval);
break;
default:
cout << "\nUnknown oper";
exit(1);
}
}
s.push(ch);
}
}
else {
cout << "\nUnknown input character";
exit(1);
}
}
}
int Express::solve()
{
// Remove the items from stack
char lastval;
while (s.gettop() > 1) {
lastval = s.pop();
switch (s.pop()) {
// Perform operation, push answer
case '+':
s.push(s.pop() + lastval);
break;
case '-':
s.push(s.pop() - lastval);
break;
case '*':
s.push(s.pop() * lastval);
break;
case '/':
s.push(s.pop() / lastval);
break;
default:
cout << "\nUnknown operator";
exit(1);
}
}
return int(s.pop());
}
// Driver code
int main()
{
char string[LEN] = "2+3*4/3-2";
// Make expression
Express* eptr = new Express(string);
// Parse it
eptr->parse();
// Solve the expression
cout << eptr->solve();
return 0;
}
4
Complejidad temporal : O(N).
Espacio Auxiliar : O(N).