c++ - 如何使用堆栈 c 评估算术表达式？

Question

到现在为止，我刚刚完成了将表达式转换为后缀表达式的操作，我尝试求值，但出了点问题，让我困惑了很长时间，我只知道如何修复它。

这是我的代码转向后缀表达式:

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

    #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 < '0' || 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;

    }

当我输入 3*(7-2)#它返回3 7 2 -

一切顺利，但我不知道接下来如何评估它，我只是将它转换为后缀表达式，我想使用堆栈对其进行评估。

Answer 1

在转换为波兰表示法时，您根本没有考虑运算符的优先级。很难给出完整的代码，但假设我们沿着 strBuild 构建一个字符串，我就是这样做的。

转换为 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 应该是 RPN 字符串。现在来评估。

评估

        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(); 弹出评估值并返回。现在对于你的主要疑问，我没有回答，因为你没有处理它，这就是你如何处理优先级问题:

enum OperatorPrecedence { Add, Minus, Mult, Div, Brackets };

    int GetExprPrecedence(string 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;
    }

请注意伪代码类似于 C-Sharp，因为这是我的工作。我已尽我最大努力使它看起来是算法化的并且不模糊，以便您可以与您的代码相关联。我的算法的结果:

请注意，我使用方括号 [ 而不是圆形 ( 作为我的表达式。最终答案是 15。