10 svar · 375 visningar · startad av Gein
Jag har skrivit en datastruktur med dess funktioner för att hantera och räkna ut enkla aritmetiska uttryck. Den tar heltalskonstanter, negation, addition och multiplikation. Använder funktionspekare när jag skapar ett uttryck. Nu är problemet ett jag ska även kunna skriva ut ett uppbyggt uttryck. Jag har nästan fått det att funka. Eller rättare sagt, det fungerar, men det blir onödigt många paranteser, det är tänkt att den bara ska skriva ut de paranteser som är nödvändiga.
T.ex (2+3)*2 är bra, men inte ((2+3)*(2)).. osv
Några tips på hur jag ska lösa problemet? Jag antar att jag är tvungen att titta i förväg hur resten av deluttrycket ser ut för att veta om paranteser är nödvändigt, men då jag använder funktionspekare och inte taggar så ser jag ju inte vad ett uttryck är av för typ (INT, NEG, ADD eller MUL).
Det är en j*vla massa kod men jag hoppas nån har lust att kolla och hjälpa mej.
Koden:
#include <stdio.h>
typedef struct expr {
int(*m_pfnFunc)(struct expr*, int wtdFlag);
union{
struct { int num; } integer;
struct { struct expr *negexpr; } negative;
struct { struct expr *expr1; struct expr *expr2; } add;
struct { struct expr *expr1; struct expr *expr2; } mul;
} u;
}expr;
int eval_expr(expr *pExpr){
return pExpr->m_pfnFunc(pExpr, 0);
}
expr *allocExpr(){
return (expr*)malloc(sizeof(expr));
}
int exprOp_int(expr *pExpr, int wtdFlag){
if (wtdFlag == 0){
printf("INT: %d\n", pExpr->u.integer.num);
return pExpr->u.integer.num;
}else{
printf("%d",pExpr->u.integer.num);
}
}
int exprOp_neg(expr *pExpr, int wtdFlag){
if (wtdFlag == 0){
int val = -eval_expr(pExpr->u.negative.negexpr);
printf("NEG: %d\n", val);
return val;
}else{
int val;
printf("-(");
val = -print_expr(pExpr->u.negative.negexpr);
printf(")");
}
}
int exprOp_add(expr *pExpr, int wtdFlag){
if (wtdFlag == 0){
int val1 = eval_expr(pExpr->u.add.expr1);
int val2 = eval_expr(pExpr->u.add.expr2);
printf("ADD: %d + %d\n", val1, val2);
return val1 + val2;
}else{
int val1, val2;
printf("(");
val1 = print_expr(pExpr->u.add.expr1);
printf("+");
val2 = print_expr(pExpr->u.add.expr2);
printf(")");
}
}
int exprOp_mul(expr *pExpr, int wtdFlag){
if (wtdFlag == 0){
int val1 = eval_expr(pExpr->u.mul.expr1);
int val2 = eval_expr(pExpr->u.mul.expr2);
printf("MUL: %d * %d\n", val1, val2);
return val1 * val2;
}else{
int val1, val2;
printf("(");
val1 = print_expr(pExpr->u.mul.expr1);
printf("*");
val2 = print_expr(pExpr->u.mul.expr2);
printf(")");
}
}
expr *create_expr_int(int(*pfnFunc)(struct expr*, int wtdFlag), int value){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.integer.num = value;
return pExpr;
}
expr *create_expr_neg(int(*pfnFunc)(struct expr*, int wtdFlag), expr *pExpr1){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.negative.negexpr = pExpr1;
return pExpr;
}
expr *create_expr_add(int(*pfnFunc)(struct expr*, int wtdFlag), expr *pExpr1, expr *pExpr2){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.add.expr1 = pExpr1;
pExpr->u.add.expr2 = pExpr2;
return pExpr;
}
expr *create_expr_mul(int(*pfnFunc)(struct expr*, int wtdFlag), expr *pExpr1, expr *pExpr2){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.mul.expr1 = pExpr1;
pExpr->u.mul.expr2 = pExpr2;
return pExpr;
}
expr *mk_int_expr(int value){
return create_expr_int(exprOp_int, value);
}
expr *mk_neg_expr(expr *pExpr){
return create_expr_neg(exprOp_neg, pExpr);
}
expr *mk_add_expr(expr *pExpr1, expr *pExpr2){
return create_expr_add(exprOp_add, pExpr1, pExpr2);
}
expr *mk_mul_expr(expr *pExpr1, expr *pExpr2){
return create_expr_mul(exprOp_mul, pExpr1, pExpr2);
}
print_expr(expr *pExpr){
return pExpr->m_pfnFunc(pExpr, 1);
}
int main(){
expr *pExpr = mk_mul_expr(mk_add_expr(mk_int_expr(2), mk_int_expr(3)), mk_int_expr(2));
//expr *pExpr = mk_add_expr(mk_neg_expr(mk_int_expr(2)), mk_int_expr(4));
//expr *pExpr = mk_mul_expr(mk_neg_expr(mk_add_expr(mk_int_expr(2), mk_int_expr(3))), mk_neg_expr(mk_int_expr(2)));
printf("Calling eval_expr() on root expression\n");
printf("RESULT: %d\n", eval_expr(pExpr));
print_expr(pExpr);
printf("\n");
}
Det där var fränt och jag bara myser.. :D
Men för att resonera kring ditt problem.. om det är endast utskriften som ska "redigeras" så har du ju faktiskt redan skapat "taggar" med paranteserna och behöver då endast lägga till en parser för att snygga till uttrycket. Så istället för att skriva ut under beräkningen, så bygg en sträng som du sedan låter en parser löpa igenom innan den slutligen skrivs ut. Inte helt trivialt, men om du exempelvis läst automat-teori förstår du nog vad jag menar.
Jag tror inte riktigt jag förstår hur du menar. Jag ska inte parsa en sträng för att bygga upp ett uttryck. Det slipper jag (ja det är en inlämningsuppgift) men jag ska ha en void print(e) som skriver ut uttrycket e. Alltså måste jag ju traversera hela uttrycket för att skriva ut det....
(!) Nu förstår jag hur du menar.. att jag låter det vara som det är nu, bara att jag parsar det uttryck som skrivs ut och rensar ut onödiga paranteser?
(!) Nu förstår jag hur du menar.. att jag låter det vara som det är nu, bara att jag parsar det uttryck som skrivs ut och rensar ut onödiga paranteser?
Jepp, det var så jag menade. :)
Okej, får se om jag klarar att fixa en sån funktion. Hur ska den parsern funka då? Då måste man komma ihåg vart man har paranteser, och på något sätt se om de är nödvändiga eller inte.
Tja.. fundera kring när de är nödvändiga. Vid operatorn * bör de ju exempelvis finnas med. Så om du först hittar ett '(' följt av 'xx * yy' så vet du att om det står ett ')' efter yy samt en annan operator än * efter slutparantes så har du anledning att ha första och sista parantesen kvar.
Det är lättare att förklara med en skiss än att skriva ned det, men parantesproblemet går inte att utreda som ett reguljärt uttryck utan det måste till nåt annat som exempelvis har ett internt "minne". Du får helt enkelt hitta på en lämplig algoritm som itererar strängen. Du skulle ju då kunna bygga ytterligare en ny sträng genom att kopiera valda bitar av den första. Dvs skapa en algortim som dels tittar på vad som är kopierat och vad som står på tur att kopieras - ett antal ggr, tecken för tecken. En lämplig startpunkt kan ju vara från mitten av den första strängen...
Finns en del att hitta om tekniken jag åsyftar om man söker på google med nyckelorden PDA och "Turing Machines".
Jag sitter o funderar på om det här verkligen är den enklaste lösningen på mitt problem. Det borde kunna gå att göras på enklare sätt tycker jag, utan att behöva parsa uttrycket alls. *funderar*
Att fundera är inte onyttigt :e
vet inte om lösningen blev så jättesnygg.. men det funkar bra! :)
#include <stdio.h>
enum expr_tag { IS_NULL, IS_INT, IS_NEG, IS_ADD, IS_MUL};
typedef struct expr {
int(*m_pfnFunc)(struct expr*, int wtdFlag, enum expr_tag, int iOrder );
union{
struct { int num; } integer;
struct { struct expr *negexpr; } negative;
struct { struct expr *expr1; struct expr *expr2; } add;
struct { struct expr *expr1; struct expr *expr2; } mul;
} u;
}expr;
int eval_expr(expr *pExpr){
eval_exprAux(pExpr, IS_NULL, 1);
}
int eval_exprAux(expr *pExpr, enum expr_tag last, int iOrder ){
return pExpr->m_pfnFunc(pExpr, 0, last, 1);
}
expr *allocExpr(){
return (expr*)malloc(sizeof(expr));
}
int exprOp_int(expr *pExpr, int wtdFlag, enum expr_tag last, int iOrder){
if (wtdFlag == 0){
printf("INT: %d\n", pExpr->u.integer.num);
return pExpr->u.integer.num;
}else{
printf("%d",pExpr->u.integer.num);
}
}
int exprOp_neg(expr *pExpr, int wtdFlag, enum expr_tag last, int iOrder){
if (wtdFlag == 0){
int val = -eval_exprAux(pExpr->u.negative.negexpr, IS_NEG, 1);
printf("NEG: %d\n", val);
return val;
}else{
if (iOrder == 1){
printf("-");
-print_exprAux(pExpr->u.negative.negexpr, IS_NEG, 1);
}else{
printf("(-");
-print_exprAux(pExpr->u.negative.negexpr, IS_NEG, 1);
printf(")");
}
}
}
int exprOp_add(expr *pExpr, int wtdFlag, enum expr_tag last, int iOrder){
if (wtdFlag == 0){
int val1 = eval_exprAux(pExpr->u.add.expr1, IS_ADD, 1);
int val2 = eval_exprAux(pExpr->u.add.expr2, IS_ADD, 2);
printf("ADD: %d + %d\n", val1, val2);
return val1 + val2;
}else{
switch(last){
case IS_MUL: case IS_NEG:{
printf("(");
print_exprAux(pExpr->u.add.expr1, IS_ADD, 1);
printf("+");
print_exprAux(pExpr->u.add.expr2, IS_ADD, 2);
printf(")");
break;
}
case IS_ADD: case IS_NULL:{
print_exprAux(pExpr->u.add.expr1, IS_ADD, 1);
printf("+");
print_exprAux(pExpr->u.add.expr2, IS_ADD, 2);
break;
}
}
}
}
int exprOp_mul(expr *pExpr, int wtdFlag, enum expr_tag last, int iOrder){
if (wtdFlag == 0){
int val1 = eval_exprAux(pExpr->u.mul.expr1, IS_MUL, 1);
int val2 = eval_exprAux(pExpr->u.mul.expr2, IS_MUL, 2);
printf("MUL: %d * %d\n", val1, val2);
return val1 * val2;
}else{
/*
switch (last){
case IS_NULL ||
}
int val1, val2;
printf("(");
val1 = print_exprAux(pExpr->u.mul.expr1, IS_MUL);
printf("*");
val2 = print_exprAux(pExpr->u.mul.expr2, IS_MUL);
printf(")");
*/
print_exprAux(pExpr->u.mul.expr1, IS_MUL, 1);
printf("*");
print_exprAux(pExpr->u.mul.expr2, IS_MUL, 2);
}
}
expr *create_expr_int(int(*pfnFunc)(struct expr*, int wtdFlag, enum expr_tag last, int iOrder), int value){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.integer.num = value;
return pExpr;
}
expr *create_expr_neg(int(*pfnFunc)(struct expr*, int wtdFlag, enum expr_tag last, int iOrder), expr *pExpr1){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.negative.negexpr = pExpr1;
return pExpr;
}
expr *create_expr_add(int(*pfnFunc)(struct expr*, int wtdFlag, enum expr_tag last, int iOrder), expr *pExpr1, expr *pExpr2){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.add.expr1 = pExpr1;
pExpr->u.add.expr2 = pExpr2;
return pExpr;
}
expr *create_expr_mul(int(*pfnFunc)(struct expr*, int wtdFlag, enum expr_tag last, int iOrder), expr *pExpr1, expr *pExpr2){
expr *pExpr = allocExpr();
pExpr->m_pfnFunc = pfnFunc;
pExpr->u.mul.expr1 = pExpr1;
pExpr->u.mul.expr2 = pExpr2;
return pExpr;
}
expr *mk_int_expr(int value){
return create_expr_int(exprOp_int, value);
}
expr *mk_neg_expr(expr *pExpr){
return create_expr_neg(exprOp_neg, pExpr);
}
expr *mk_add_expr(expr *pExpr1, expr *pExpr2){
return create_expr_add(exprOp_add, pExpr1, pExpr2);
}
expr *mk_mul_expr(expr *pExpr1, expr *pExpr2){
return create_expr_mul(exprOp_mul, pExpr1, pExpr2);
}
print_expr(expr *pExpr){
print_exprAux(pExpr, IS_NULL, 1);
}
print_exprAux(expr *pExpr, enum expr_tag last, int iOrder){
return pExpr->m_pfnFunc(pExpr, 1, last, iOrder);
}
int main(){
//expr *pExpr = mk_mul_expr(mk_add_expr(mk_int_expr(2), mk_int_expr(3)), mk_int_expr(2));
//expr *pExpr = mk_add_expr(mk_int_expr(4),mk_neg_expr(mk_int_expr(2)));
//expr *pExpr = mk_mul_expr(mk_neg_expr(mk_add_expr(mk_int_expr(2), mk_int_expr(3))), mk_neg_expr(mk_int_expr(2)));
//expr *pExpr = mk_mul_expr(mk_add_expr(mk_int_expr(1), mk_int_expr(2)), mk_add_expr(mk_int_expr(3), mk_int_expr(4)));
expr *pExpr = mk_mul_expr(mk_neg_expr(mk_int_expr(2)),mk_mul_expr(mk_mul_expr(mk_add_expr(mk_int_expr(5), mk_int_expr(7)), mk_int_expr(2)), mk_neg_expr(mk_int_expr(1))));
;
printf("Calling eval_expr() on root expression\n");
printf("RESULT: %d\n", eval_expr(pExpr));
print_expr(pExpr);
printf("\n");
}
Ja se... du petade ju in ett allt-i-ett kit! Fungerar detta för din redovisning är det ju kalas :)
Jag hoppas verkligen det duger! Fick lägga in ett par till argument i funktionerna så det ser lite rörigare ut, men vafan! :)