1

到目前为止，我刚刚完成表达式转换为后缀表达式，我尝试评估但出现问题并让我很长时间感到困惑，我只知道如何修复它。

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

#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 -

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

4

1 回答 1

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。

于 2013-10-18T06:53:15.417 回答