C中使用堆栈的计算器

Question

我正在尝试用 c 语言创建一个计算器，它可以优先计算并为以下示例获得正确的结果:

((5+5)/3)*3) --> 9

((1+2) * 3) --> 9

我下面的代码可以计算出这些例子。但是对于这样的事情

(2+5) * (2+5)，我的程序给出了错误的答案。

我正在使用 2 个堆栈。一种用于运算符，一种用于数字。它的工作原理是:
如下:

((4 - 2) * 5) + 3 --> 普通中缀表达式:
+ * - 4 2 5 3

伪代码:

Read + (an operation), push it onto the stack,  
Read * (an operation), push it onto the stack,  
Read - (an operation), push it onto the stack,  
Read 4 (a number), the top of the stack is not a number, so push it onto the     stack.  
Read 2 (a number), the top of the stack is a number, so pop from the stack     twice, you get 4 - 2, calculate it (2), and push the result (2) onto the stack.      
Read 5 (a number), the top of the stack is a number, so pop from the stack twice, you get 2 * 5, push the result (10) onto the stack.  
Read 3 (a number), the top of the stack is a number, so pop from the stack twice, you get 3 + 10, push the result (13) onto the stack.  
Nothing left to read, pop from the stack and return the result (13).  

实际代码:

#include <stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 102

typedef struct
{
    char stk[MAXSIZE];
    int top;
}STACK;

typedef struct stack
{
    int stk[MAXSIZE];
    int itop;
}INT_STACK;

STACK s;
INT_STACK a;
void push(char);
char  pop(void);
void display(void);

int main()
{
  a.itop = 0;
  char string[MAXSIZE],vyb,vyb2;
  int cislo1,cislo2,vysledok;

  while (gets(string) != NULL){
    for(int j = strlen(string); j > 0; j--){
      if(string[j] == '*' || string[j] == '/' || string[j] == '+' || string[j] == '-')
        push(string[j]);
    }

    //display();
    for(int j = 0; j < strlen(string); j++){
      if(isdigit(string[j])&&!(a.itop)){
        //display();
        char pomoc[2];
        pomoc[0] = string[j];
        pomoc[1] = '\0';
        int_push(atoi(pomoc));
      }
      else if(isdigit(string[j])&&(a.itop)){
         cislo1 = int_pop();
         vyb2 = pop();
         char pomoc[2];
         pomoc[0] = string[j];
         pomoc[1] = '\0';
         cislo2 =  atoi(pomoc);
         if(vyb2 == '+')
            vysledok = cislo1+cislo2;
         else if(vyb2 == '-')
            vysledok = cislo1-cislo2;
         else if(vyb2 == '*')
            vysledok = cislo1*cislo2;
         else if(vyb2 == '/')
            vysledok = cislo1 / cislo2;
         //printf("  v   %d",vysledok);
         int_push(vysledok);
      }
    }
    printf("%d\n",int_pop());
  }
}

/*  Function to add an element to the stack */
void push (char c)
{
    s.top++;
    s.stk[s.top] = c;
    //printf ("pushed element is = %c \n", s.stk[s.top]);
}

/*  Function to delete an element from the stack */
char pop ()
{
    char num = s.stk[s.top];
   // printf ("poped element is = %c\n", s.stk[s.top]);
    s.top--;
    return(num);
}

int empty()
{
    if (s.top == - 1)
    {
        printf ("Stack is Empty\n");
        return (s.top);
    }
    return 1;
}

void display ()
{
    int i;
    if (!empty)
    {
        printf ("Stack is empty\n");
        return;
    }
    else
    {
        printf ("\n The status of the stack is \n");
        for (i = s.top; i >= 0; i--)
        {
            printf ("%c\n", s.stk[i]);
        }
    }
    printf ("\n");
}

void int_push (int c)
{
    a.itop++;
    a.stk[a.itop] = c;
    //printf ("pushed element is = %d \n", a.stk[a.itop]);
}

/*  Function to delete an element from the stack */
int int_pop ()
{
    int num = a.stk[a.itop];
   // printf ("poped element is = %d\n", a.stk[a.itop]);
    a.itop--;
    return(num);
}

有没有其他方法可以创建一个优先计算器，可以给出很好的答案？
感谢您的回复

Answer 1

放置断点 - 您将得到以下表达式:+ + * 2 5 2 5。问题在于，您的解释器将其解释为 (2+5+2)*5 而不是 (2+5) * (2+5)。

那么，您可能想知道如何解决这个问题。没有简单的单一解决方案 - 您可以修复自己的解释器或构建一个全新的机制，因为构建表达式的方式无法处理超过一对的分词。

例如，您可能想要在单独构建表达式之前计算括号中的所有值，可能在括号接受的情况下使用递归 - 但是如果您实际上选择使用该方法，您可能想要更改您的方式完全使用表达式，因为这是一种不同的方法。

如果您需要我展示实际的代码示例以使用您编写的部分代码进一步解释这一点，请提出要求，我会编辑并提供您需要的内容。

无论哪种方式，我真的建议您总体上与解释器一起工作 - 您真的可以学到很多关于分析字符串和使用不同输入的知识，人们甚至可以用计算器做与您类似的事情 before

编辑:您要求提供示例，所以现在开始 - 这是使用递归的完全不同方法的示例。这样，您一次只处理一对括号，因此您不会遇到当前遇到的问题。注意 - 我基于此的来源(几乎复制粘贴了线程的编辑和一些个人评论)来自堆栈交换上的代码审查，你可以看到它 here 如果您有兴趣。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void getInput(char * in) {
 printf("> ");
 fgets(in, 256, stdin);
}

int isLeftParantheses(char p) {
if (p == '(') return 1;
else return 0;
}

int isRightParantheses(char p) {
if (p == ')') return 1;
else return 0;
}

int isOperator(char p) {
if (p == '+' || p == '-' || p == '*' || p == '/') return p;
else return 0;
}

int performOperator(int a, int b, char p) {
 switch(p) {
    case '+': return a+b;
    case '-': return a-b;
    case '*': return a*b;
    case '/':
        if (b == 0) { printf("Can't divide by 0, aborting...\n"); exit(1); }  // now we dont want the world to expload here do we.
        return a/b;
    default:
       puts("Bad value in switch.\n"); // A replacement which was mentioned in the thread- better have a default response just in case something goes wrong.
       break;
 }
return 0;
 }


char isDigit(char p) {
if (p >= '0' && p <= '9') return 1;
else return 0;
}

int charToDigit(char p) {
if (p >= '0' && p <= '9') return p - '0';
else return 0;
}

int isNumber(char * p) {
while(*p) {
    if (!isDigit(*p)) return 0;
    p++;
}
return 1;
}

int len(char * p)
{
 return (int) strlen(p); // This was bugged in the source, so I fixed it like the thread advised.
}

int numOfOperands(char * p) {
int total = 0;
while(*p) {
    if (isOperator(*p)) total++;
    p++;
}
return total+1;
}

int isMDGRoup(char *p)
{

for(; *p; p++) // used to be a while loop in the source, but this is better imho. more readable, also mentioned on the thread itself.
{
    if (!isDigit(*p) && *p != '/' && *p != '*') return 0;
}
return 1;
}
int getLeftOperand(char * p, char * l) {
// Grab the left operand in p, put it in l,
//and return the index where it ends.
int i = 0;

// Operand is part of multi-*/ group
if (isMDGRoup(p)) {
    while(1) {
        if (*p == '*' || *p == '/') break;
        l[i++] = *p++;
    }
    return i;
}

// Operand is in parantheses (so that's how you write it! sorry for my bad english :)
if(isLeftParantheses(*p)) {
    int LeftParantheses = 1;
    int RightParantheses= 0;
    p++;
    while(1) {
        if (isLeftParantheses(*p))  LeftParantheses++;
        if (isRightParantheses(*p)) RightParantheses++;

        if (isRightParantheses(*p) && LeftParantheses == RightParantheses)
            break;
        l[i++] = *p++;
    }
    // while (!isRightParantheses(*p)) {
    //  l[i++] = *p++;
    // }
    l[i] = '\0';
    return i+2;
}

// Operand is a number
while (1) {
    if (!isDigit(*p)) break;
    l[i++] = *p++;
}
l[i] = '\0';
return i;
}

int getOperator(char * p, int index, char * op) {
*op = p[index];
return index + 1;
}

int getRightOperand(char * p, char * l) {
// Grab the left operand in p, put it in l,
//and return the index where it ends.
while(*p && (isDigit(*p) || isOperator(*p) ||
             isLeftParantheses(*p) || isRightParantheses(*p))) {
    *l++ = *p++;
}
*l = '\0';

return 0;
}

int isEmpty(char * p) {
// Check if string/char is empty
if (len(p) == 0) return 1;
else return 0;
}

int calcExpression(char * p) {
// if p = #: return atoi(p)
//
// else:
//  L = P.LeftSide
//  O = P.Op
//  R = P.RightSide
//  return PerformOp(calcExpression(L), calcExpression(R), O)

// ACTUAL FUNCTION

// if p is a number, return it
if (isNumber(p)) return atoi(p);

// Get Left, Right and Op from p.
char leftOperand[256] = ""; char rightOperand[256]= "";
char op;

int leftOpIndex   = getLeftOperand(p, leftOperand);
int operatorIndex = getOperator(p, leftOpIndex, &op);
int rightOpIndex  = getRightOperand(p+operatorIndex, rightOperand);

printf("%s, %c, %s", leftOperand, op, rightOperand);
getchar();

if (isEmpty(rightOperand)) return calcExpression(leftOperand);

return performOperator(
    calcExpression(leftOperand),
    calcExpression(rightOperand),
    op
);
}

int main()
{
char in[256];
while(1) {
    // Read input from user
    getInput(in);
    if (strncmp(in, "quit", 4) == 0) break;

    // Perform calculations
    int result = calcExpression(in);
    printf("%d\n", result);
}
}