INFORME DEL ANALISIS DEL CODIGO
ESTUDIANTE: JOS ALEJANDRO MORENO AGUDELO
CODIGO: 1088323569
MATERIA: PROGRAMACIN IV
============================================================
CODIGO DEL PAQUETE TEXT:
-------------------------------------------------------------------------------------------------------------------------
PARA EL CDIGO DE LA CALCULADORA QUE SE ENVI AL CORREO, SE PROCEDE INGRESANDO A
LA CLASE "TOKEN" EN LA CUAL SE ENCUENTRA QUE ES UNA INTERFACE QUE POSEE UN MTODO
MATCH(). SE ENTIENDE EN EL CONTEXTO DEL PROGRAMA QUE LA INTERFACE "TOKEN" ES UN
ELEMENTO DE LA SINTAXIS DE LAS EXPRESIONES ARITMTICAS DEL PROGRAMA.
AS MISMO SE PROCEDE AL ANALISIS DE LA CLASE "TOKENSET", LA CUAL BSICAMENTE ES UN
OBJETO QUE ALMACENA LAS DISTINTAS EXPRESIONES REGULARES QUE SE RECONOCERN EN
EL PROGRAMA, ADEMS DE QUE DADO UNA EXPRESION CLASIFICA QUE TIPO DE TOKEN SER,
BASADO EN LAS ESPECIFICACIONES PREVIAS DE LOS TIPOS DE TOKENS.
DE ESTA MANERA, SE ENCUENTRA UNA RELACIN DIRECTA ENTRE LAS CLASES "WORDTOKEN" Y
"SIMPLETOKEN", SIENDO SIMPLETOKEN UN SIMPLE ELEMENTO, EN CAMBIO WORDTOKEN ES
TODA UNA LINEA DE ELEMENTOS.
A SU VEZ SIMPLETOKEN COMPARA TOKENS PARA LOS CUALES EXISTE SOLAMENTE UNA POSIBLE
ESCRITURA. DE ESTA MANERA, WORDTOKEN ES UN SIMPLETOKEN, DE UN MAYOR TAMAO.
SE ENCUENTRA ADEMS QUE EL OBJETO "BEGINTOKEN", NO HACE NADA EN REALIDAD, MS
QUE SERVIR COMO VALOR INICIAL, QUE NO RECONOCER (O HAR MATCH) CON NINGUNA
EXPRESIN, SLO SIRVE PARA GENERAR UNA INICIALIZACIN.
POR OTRA PARTE, LA CLASE "REGEXTOKEN" TIENE UNA FUNCIONALIDAD MUY PARTICULAR,
DEBIDO A QUE DADO UNA EXPRESION MUY PARTICULAR CREA UN TOKEN Y LO ENVA A
TOKENSET. ESTA CLASE UTILIZA EL PAQUETE DE EXPRESIONES REGULARES DE JAVA PARA
COMPARAR LA ENTRADA DE LOS DATOS CON LAS ESPECIFICACIONES DEL PROGRAMA.
SIN EMBARGO, LA CLASE "PARSEFAILURE" ES SIMPLEMENTE AQUELLA QUE ESTABLECE LOS
ERRORES DEL PROGRAMA.
POR LTIMO, LA CLASE "SCANNER" TIENE COMO FIN LTIMO EL DE RECIBIR LOS DISTINTOS
SIMBOLOS QUE SE QUIEREN RECONOCER, HACIENDOLOS PARTE DEL TOKENSET Y LUEGO CREA
UNA CADENA DE CARACTERES PARA PROBAR QUE EL SIMBOLO FUE CREADO CORRECTAMENTE,
Y EN CASO DE NO HABERLO SIDO ENTONCES CREA UNA ASERCION.
POR TANTO LA CLASE SCANNER BUSCA TOKENS EN UN ARREGLO ESPECIFICO, LEYENDO
CARACTERES DE LA ENTRADA.
CUANDO SE EJECUTA EL CDIGO SE OBSERVA QUE NO ARROJA NINGN MENSAJE DADO QUE
TODOS LOS SIMBOLOS FUERON RECONOCIDOS Y CREADOS CORRECTAMENTE, PERO AL
ALTERAR LA CADENA DE PRUEBA CON UN VALOR INESPERADO ARROJA ERROR, DADO QUE
DICHO SIMBOLO NO FUE CREADO Y POR LO TANTO NO FUE RECONOCIDO.
PARA RECONOCER LOS SIMBOLOS BUSCADOS EN LA CALCULADORA, SE CREA UN OBJETO DE
TIPO SCANNER Y SE LE INSERTA UNA CADENA DE CARECTERES ESPECIFICANDO EL TIPO DE
DATO Y LUEGO GENERANDO UNA EXPRESION CON DICHO SIMBOLO, REVISANDO QUE EL TIPO
DE DICHO SIMBOLO COINCIDA CON LO ESTABLECIDO.
POR EJEMPLO YO A SCANNER LE INTRODUSCO '+' QUE ES SUMA, LUEGO LE PASO '+12346533' Y
AL RECONOCER ME DEBE RETORNAR SUMA, EN CASO CONTRARIO SIGNIFICARA ERROR.
ALGORITMO SHUNTING YARD:
EL ALGORITMO SHUTING YARD ES UN ANALIZADOR SINTACTICO QUE POSEE DOS PILAS
CONVIERTIENDO EXPRESIONES EN NOTACION INFIJA, EN NOTACION POSTFIJA, ALMACENANDO
EN UNA PILA LOS NUMEROS Y EN OTRA LAS FUNCIONES.
DE ESTA MANERA LA PILA DE SALIDA SON LOS NUMEROS Y LA DE ENTRADA SON LOS
OPERADORES, POR TANTO AL ENCONTRARSE CON UN NUMERO PASA DIRECTO A LA PILA DE
SALIDA EN CAMBIO LOS OPERADORES SON INSERTADOS EN LA PILA DE SALIDA, AL FINAL
TODOS LOS OPERADORES SON PAULATINAMENTE RETIRADOS EN ORDEN DE PROCEDENCIA SI
SON DIFERENTES, POR TANTO SIEMPRE DEBE IR UN OPERADOR DE MAYOR PROCEDENCIA Y
UNO DE MENOR PROCEDENCIA.
POR TANTO AL FINAL SE FORMA LA EXPRESION EN FORMA POSTFIJA
Implementacin en C++
//**************************************
// Name: Shunting Yard
// Description:This program takes asks for an expression and parses it
using the Shunting Yard Algorithm. The expression must have a space
between every single function, operator, and number (unless it is a
negative number, in which case the negative sign must be adjacent to the
digit). For instance, cos ( ( 1.3 + 1 ) ^ ( 1 / 3 ) ) - log ( -2 * 3 / -
14 ) is valid. If there are any problems with the input, then the program
will crash unexpectedly. There is support for floating point numbers, the
operators +, -, *, /, and ^, and the functions sin, cos, and log.
However, the operators and functions can be easily expanded by looking at
the methods is_func, is_op, and operate.
// By: Chirag Sakhuja
//
//This code is copyrighted and has// limited [Link] see
[Link]
[Link]/vb/scripts/[Link]?txtCodeId=13263&lngWId=3//for
details.//**************************************
#include<iostream>
#include<string>
#include<sstream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
bool is_func(string);
bool is_op(string);
bool is_left(char);
int get_prec(char);
float operate(float, string);
float operate(float, float, char);
struct output_data
{
float num;
string opf;
bool is_num;
output_data(float n)
{
num = n;
is_num = true;
}
output_data(string o)
{
opf = o;
is_num = false;
}
};
int main()
{
cout << "Input Expression: ";
string in;
getline(cin, in);
stringstream str (in);
queue<output_data> output;
stack<string> opfs;
string part;
while(str >> part)
{
if(!is_func(part) && !is_op(part))
{
output_data temp ((float)atof(part.c_str()));
[Link](temp);
}
else if(is_func(part))
{
[Link](part);
}
else
{
char op = part[0];
int prec = get_prec(op);
bool left = is_left(op);
if(op != '(' && op != ')')
{
while(![Link]() && (left && prec <=
get_prec([Link]()[0])) || (!left && prec < get_prec([Link]()[0])))
{
[Link]([Link]());
[Link]();
}
string temp (1, op);
[Link](temp);
}
if([Link]() == 0 || op == '(')
{
string temp (1, op);
[Link](temp);
}
if(op == ')')
{
while([Link]()[0] != '(')
{
[Link]([Link]());
[Link]();
}
[Link]();
if(is_func([Link]()))
{
[Link]([Link]());
[Link]();
}
}
}
}
while(![Link]())
{
[Link]([Link]());
[Link]();
}
stack<float> eval;
while(![Link]())
{
output_data out = [Link]();
[Link]();
if(out.is_num)
{
[Link]([Link]);
}
else if(is_func([Link]))
{
float num = [Link]();
[Link]();
float res = operate(num, [Link]);
[Link](res);
}
else
{
float num1 = [Link]();
[Link]();
float num2 = [Link]();
[Link]();
float res = operate(num2, num1, [Link][0]);
[Link](res);
}
}
cout << [Link]() << endl;
return 0;
}
//checks whether the string is a function or not.
bool is_func(string check)
{
if(check == "sin" || check == "cos" || check == "log")
return true;
return false;
}
//checks whether the string is an operator or not.
bool is_op(string check)
{
if([Link]() > 1)
return false;
switch(check[0])
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '(':
case ')':
return true;
default:
return false;
}
}
bool is_left(char op)
{
switch(op)
{
case '+':
case '-':
case '*':
case '/':
return true;
default:
return false;
}
}
int get_prec(char op)
{
switch(op)
{
case '^':
return 2;
case '*':
case '/':
return 1;
case '+':
case '-':
return 0;
default:
return -1;
}
}
//evaluates a function.
float operate(float num, string func)
{
if(func == "sin")
return sin(num);
else if(func == "cos")
return cos(num);
else if(func == "log")
return log10(num);
return 0;
}
//evaluates an operator.
float operate(float num1, float num2, char op)
{
switch(op)
{
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
case '^':
return pow(num1, num2);
default:
return 0;
}
}
EL PROGRAMA RECIBE UN STRING EN DONDE ESTAR LA EXPRESIN ARITMTICA, EN DONDE
CADA ELEMENTO ESTA SEPARADO POR UN ESPACIO. EL PROGRAMA TOMA CADA ELEMENTO, Y
COMIENZA COMPARANDOLO CON LAS FUNCIONES ( SIN, COS, LOG) Y CON LAS OPERACIONES
( +,-,*,/,^,(,) ), EN CASO DE NO ESTAR EN NINGUNA DE LAS ANTERIORES CLASIFICACIONES,
DICHO SIMBOLO SE CONSIDERA UN NMERO Y ES INSERTADO EN LA COLA, PERO SI ES UNA
FUNCIN SE INSERTA EN LA PILA. POR OTRA PARTE, SI SE TIENE UN OPERADOR, SE INICIA POR
BUSCAR SU PRECEDENCIA. MIENTRAS QUE LO QUE SE TENGA NO SEA UN PARENTESIS, SE
RETIRA EL OPERADOR DE LA COLA, Y SE OPERA SOBRE LOS NUMEROS CORRESPONDIENTES. AL
FINAL SE REALIZA LAS OPERACIONES CORRESPONDIENTES HASTA QUE LA COLA ESTE VACA.
IMPLEMENTACION PYTHON
'''Hey, it's public domain :)'''
class MismatchedParenthesesException(Exception):
'''Raised when Djikstrer detects that there is something wrong with
separators or parentheses'''
pass
class Djikstrer:
'''This class performs conversion from infix expressions to Reverse
Polish Notation using Djikstra's shunting yard
algorithm. Function run() accepts a list of tokens(yes, the expression
needs to be tokenized first) and after run() finishes
there is a list of tokens in class' attribute 'output' in RPN order. New
operators can be added below. Smaller precedence
means the operator will get executed later, ie. multiplication has
greater precedence than addition. Obviously, precedence is set in
op_prec dictionary. assoc, lassor and rassoc dictionaries specify
whether the operators are associative, left-associative or
right-associative. Note: one class can perform many conversions, as
'run' method cleans the stack and output before analysis.
Another note: watch out for unary minus(ie. -5) passed as two tokens, as
it will certainly screw the stuff up.
Same with unary plus(but who would type something like that?'''
operators = ('&&','||','+','-','*','/','^')
op_prec = {'+':3,'-':3,'*':4,'/':4,'^':5,'&&':6,'||':6}
assoc = {'+':True,'-
':False,'*':True,'/':False,'^':False,'||':True,'&&':True}
lassoc = {'+':True,'-
':True,'*':True,'/':True,'^':False,'||':True,'&&':True}
rassoc = {'+':True,'-
':False,'*':True,'/':False,'^':True,'||':True,'&&':True}
def _isparenthesis(self, token):
return (token in ('(',')'))
def _isfunction(self, token):
return not (self._isoperator(token) or self._isparenthesis(token) or
self._isnumber(token) or self._isseparator(token))
def _isseparator(self, token):
return token== ','
def _isoperator(self, token):
return token in [Link]
def _isnumber(self,x):
try:
float(x)
except:
return False
return True
def areThereOperatorsOnStack(self):
for x in [Link]:
if self._isoperator(x):
return True
return False
def sTo(self):
[Link]([Link]())
def spush(self, token):
[Link](token)
def opush(self, token):
[Link](token)
def run(self, tokenlist):
[Link] = []
[Link] = []
try:
for token in tokenlist:
[Link](token)
while [Link]():
if self._isparenthesis([Link][-1]):
raise MismatchedParenthesesException, 'Parentheses'
[Link]()
except:
raise MismatchedParenthesesException, 'Parentheses or separators'
def token(self, token):
if self._isnumber(token):
[Link](token)
return
if self._isfunction(token):
[Link](token)
return
if self._isseparator(token):
while not [Link][-1]=='(':
if len([Link])==0:
raise MismatchedParenthesesException, 'Parentheses or separators'
[Link]()
if [Link][-1]=='(':
break
return
if self._isoperator(token):
if len([Link])>0:
while self._isoperator([Link][-1]) and ((([Link][token] or
[Link][token]) and (self.op_prec[token]<=self.op_prec[[Link][-
1]])) or ([Link][token] and
(self.op_prec[token]<self.op_prec[[Link][-1]]))):
[Link]()
[Link](token)
return
if token=='(':
[Link](token)
return
if token==')':
while not [Link][-1]=='(':
if len([Link])==0:
raise MismatchedParenthesesException('Parentheses')
[Link]()
if [Link][-1]=='(':
break
[Link]()
if len([Link])==0:
return
if self._isfunction([Link][-1]):
[Link]()
ESTA IMPLEMENTACIN TIENE UNA LGICA SIMIL A LA DE LA IMPLEMENTACIN ANTERIOR,
DEBIDO A QUE ALMACENA UNA SERIE DE SIMBOLOS PREESTABLECIDOS CUYA FINALIDAD
POSTERIOR ES LA DE COMPARAR EN QU CATEGORIA ESTAN LOS DISTINTOS CARACTERES QUE
SE LEEN EN LA ENTRADA DE DATOS.
SE EJECUTA EL MISMO PROCESO DE COMPARACIN E IGUALMENTE SE HACE EL MISMO
PROCESO DE EVALUACIN CON EL ALGORITMO DE SHUNTING YARD.
IMPLEMENTACION JAVA
import [Link].*;
public class ShuntingYard {
private enum Operator
{
ADD(1), SUBTRACT(2), MULTIPLY(3), DIVIDE(4);
final int precedence;
Operator(int p) { precedence = p; }
}
private static Map<String, Operator> ops = new HashMap<String, Operator>() {{
put("+", [Link]);
put("-", [Link]);
put("*", [Link]);
put("/", [Link]);
}};
private static boolean isHigerPrec(String op, String sub)
{
return ([Link](sub) && [Link](sub).precedence >= [Link](op).precedence);
}
public static String postfix(String infix)
{
StringBuilder output = new StringBuilder();
Deque<String> stack = new LinkedList<>();
for (String token : [Link]("\\s")) {
// operator
if ([Link](token)) {
while ( ! [Link]() && isHigerPrec(token, [Link]()))
[Link]([Link]()).append(' ');
[Link](token);
// left parenthesis
} else if ([Link]("(")) {
[Link](token);
// right parenthesis
} else if ([Link](")")) {
while ( ! [Link]().equals("("))
[Link]([Link]()).append(' ');
[Link]();
// digit
} else {
[Link](token).append(' ');
}
}
while ( ! [Link]())
[Link]([Link]()).append(' ');
return [Link]();
}
}
EN ESTE CODIGO DE JAVA SE TIENE EL MISMO PROCESO, PERO CON UN TIPO ENUMERADO QUE
ES OPERADOR, EL CUAL POSEE UNA ASIGNACION DE UN NUMERO Y FUNCIONA DE LA MISMA
MANERA EVALUANDO EN PRIMER LUGAR LA PRECEDENCIA DE LOS OPERADORES PARA LUEGO
PASAR A UN ESTADO DE EVALUACIN O REALIZACIN DE OPERACIONES.
