C语言使用栈实现计算器

Question

我正在尝试用C语言创建一个计算器，可以按照优先级进行计算，并获得正确的结果，例如：

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

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

我的代码可以计算这些示例。但是对于像这样的表达式

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

我使用了两个栈，一个用于操作符，一个用于数字。它遵循以下原则：
如下：

((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);
}

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

- Jozef Bugoš

---

更好的方法是使用后缀表示法。这将需要一个堆栈（根据您的意愿，可以用于操作数或运算符）。在后缀表示法中进行计算非常简单。 - Rakholiya Jenish

(2+5)(2+5) 是一个有效的表达式吗？ - OldProgrammer

@OldProgrammer：一个缺失的星号被解释为Markdown中的关闭斜体。 - Lynn

Mauris是正确的，确实缺少了一个星号，因为这里它是一些特殊符号。 - Jozef Bugoš

你的代码无法识别输入字符串中的括号，完全忽略它们并且没有任何处理方式。这就是为什么你的计算器出现错误的原因。实际上，它甚至无法计算 3-(2-1)。 - CiaPan

Answer 1

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

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

例如，你可能希望在单独构建表达式之前计算所有括号中的值，可能在括号嵌套的情况下使用递归 - 但是如果你选择使用该方法，你可能需要完全改变与表达式的处理方式，因为这是一种不同的方法。

如果你需要我展示实际的代码示例来进一步解释这个问题，使用你编写的代码的部分，请告诉我，我会编辑并提供你所需的内容。

无论如何，我真的建议您查阅有关使用口译员的相关信息——您可以学习很多关于分析字符串和处理不同输入的知识，人们甚至使用计算器做了类似您所做的事情 before 编辑：您要求示例，那么给您一个——这是使用递归的完全不同方法的示例。这种方式，您每次只处理一对括号，因此您不会遇到当前存在的问题。注意——我基于 stack exchange 上的 codereview（基本上是从主题中复制粘贴并进行编辑的）的源代码，如果您感兴趣，可以在 此处 查看。

#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);
}
}

- A. Abramov

---

谢谢，如果您能给我展示代码示例，那将非常有帮助，这样我就可以从中学习。 - Jozef Bugoš

@JozefBugoš 你可能想看一下我的编辑。如果你感到困惑，随时可以问或查看所提到的源代码。 - A. Abramov

谢谢，我也尝试过这种方法，但当时做不好，所以现在我又尝试了另一种方法。我会看一下你编辑的代码。 - Jozef Bugoš

尝试在这里、在SO和维基百科中搜索逆波兰表达式转换算法。 - CiaPan