Comment évaluer une expression arithmétique en utilisant la stack c?

à présent, je termine juste l’expression en passant à l’expression postfixe, et j’essaie d’évaluer mais quelque chose ne va pas et me déroute longtemps, et je sais juste comment le réparer.

Voici mon code à l’expression postfixe:

#include  #include  #include  #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10 #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; Status InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if ( !s->base ) { exit(0); } s->top = s->base; s->stackSize = STACK_INIT_SIZE; return OK; } Status Push(sqStack *s, ElemType e) { //if the stack is full if ( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if ( !s->base ) { exit(0); } s->top = s->base + s->stackSize; s->stackSize += STACKINCREMENT; } //store data *(s->top) = e; s->top++; return OK; } Status Pop(sqStack *s, ElemType *e) { if ( s->top == s->base ) { return ERROR; } *e = *--(s->top); return OK; } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; char c; char e; InitStack(&s); printf("Please input your calculate expression(# to quit):\n"); scanf("%c", &c); while ( c != '#' ) { while ( c >= '0' && c <= '9' ) { printf("%c", c); scanf("%c", &c); if ( c  '9' ) { printf(" "); } } if ( ')' == c ) { Pop(&s, &e); while ( '(' != e ) { printf("%c ", e); Pop(&s, &e); } } else if ( '+' == c || '-' == c ) { if ( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if ( '(' == e ) { Push(&s, e); } else { printf("%c", e); } }while ( StackLen(s) && '(' != e ); Push(&s, c); } } else if ( '*' == c || '/' == c || '(' == c ) { Push(&s, c); } else if ( '#' == c ) { break; } else { printf("\nInput format error!\n"); return -1; } scanf("%c", &c); } while ( StackLen(s) ) { Pop(&s, &e); printf("%c ", e); } return 0; } 

Quand je mets 3 * (7-2) # il retourne 3 7 2 –

Les choses se passent bien, mais je ne sais pas comment l’évaluer ensuite, je le tourne simplement en expression postfixée et je veux l’évaluer en utilisant stack.

Vous n’avez pas du tout pris en compte la priorité des opérateurs lors de la conversion en notation polonaise. Il est difficile de donner le code complet, mais c’est comme cela que je l’ai fait en supposant que nous construisions une chaîne le long de strBuild .

Conversion en RPN

  if (token is integer) { strBuild.Append(token); strBuild.Append(" "); } else if (token is Operator) { while (isOperator(Stack.Peek())) { if (GetExprPrecedence(token) <= GetExprPrecedence(Stack.Peek())) { strBuild.Append(Stack.Pop()); strBuild.Append(" "); } else break; } Stack.Push(token); } else if (token == '(') { Stack.Push(token); } else if (token == ')') { while (Stack.Peek() != '(') { if (Stack.Count > 0) { strBuild.Append(Stack.Pop()); strBuild.Append(" "); } else { Show("Syntax Error while Parsing"); break; } } Stack.Pop(); } while (Stack.Count > 0 && isOperator(Stack.Peek())) { if (Stack.Peek() == '(' || Stack.Peek() == ')') { MessageBox.Show("All Tokens Read - Syntax Error"); break; } Stack.Pop(); } return strBuild; 

strBuild doit être la chaîne RPN. Maintenant pour évaluer.

Évaluer

  for (int i = 0; i < StrPostFix.Length; i++) { token = StrPostFix[i]; if (isOperator(token)) { switch (token) { case "/": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 / op2; break; case "*": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 * op2; break; case "+": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 + op2; break; case "-": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 - op2; break; } Stack.Push(val); } else Stack.Push(token); } return Stack.Pop(); 

return Stack.Pop(); affiche la valeur évaluée et retourne. Maintenant, pour votre doute principal auquel je n’ai pas répondu puisque vous ne vous en êtes pas occupé, voici comment vous pouvez traiter le problème de priorité:

 enum OperatorPrecedence { Add, Minus, Mult, Div, Brackets }; int GetExprPrecedence(ssortingng op) { int p = 0; switch (op) { case "(": p = (int)OperatorPrecedence .Brackets; break; case "/": p = (int)OperatorPrecedence .Div; break; case "*": p = (int)OperatorPrecedence .Mult; break; case "-": p = (int)OperatorPrecedence .Minus; break; case "+": p = (int)OperatorPrecedence .Add; break; } return p; } 

Notez que le pseudo-code ressemble à C-Sharp puisque c’est ce sur quoi je travaille. J'ai fait de mon mieux pour lui donner un aspect algorithmique et non vague afin que vous puissiez vous identifier à votre code. Résultat par mon algorithme:

entrez la description de l'image ici

Notez que j'utilise Box Brackets [ au lieu de Round ( pour mes expressions). La réponse finale était de 15.