数据结构关于用栈表达式求值

1298150336

题目如下：


输入一个算术表达式(以“=”结束)，求其值。要求表达式以“=”结束，操作数为多位实数。

1.设置两个栈：optr算符栈和opnd操作数栈。初始置opnd为空栈；起始符“=”为optr的栈底元素；

2.自左向右扫描表达式中的每个字符c：

1)若c为操作数，则进opnd栈；

2)若c为算符，则让optr栈的栈顶元素与c比较优先级：

a.若栈顶算符优先级低于刚读入的运算符c，则让刚读入的运算符c进optr栈。

b.若栈顶算符优先级高于刚读入的运算符c，则将栈顶算符退栈，送入q；同时将操作数栈opnd退栈两次，得到两个操作数b、a，对a、b进行aqb运算后，将运算结果作为中间结果推入opnd栈。

c.若栈顶运算符的优先级与刚读入的运算符c相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。

3.直到扫描到c为定界符，即optr栈的栈顶元素和当前读入的字符均为“=”，则整个表达式求值完毕。

我的代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>


#define MAXSIZE 100
typedef double DataType;
typedef struct Node
{
        DataType data[MAXSIZE];
        int top;
}SqStack;


int InitStack(SqStack &s)
{
        s.top=-1;
        return 1;
}

int StackEmpty(SqStack s)
{
        return (s.top==-1?1:0);
}

int StackFull(SqStack s)
{
        return ((s.top==MAXSIZE-1)?1:0);
}

DataType GetTop(SqStack S)//取栈顶元素
{
        if(StackEmpty(S)) return 0;
        DataType e=S.data[S.top];
        return e;
}

int Push(SqStack &s,DataType e)
{
        if(StackFull(s)) return 0;
        s.top++;
        s.data[s.top]=e;
        return 1;
}

int Pop(SqStack &s,DataType &e)
{
        if(StackEmpty(s)) return 0;
        e=s.data[s.top];
        s.top--;
        return 1;
}

int In(char ch)//判断字符是否为运算符
{
        int flag=0;
        char OP[7]={'+','-','*','/','(',')','='};
        for(int i=0;i<7;i++)
        {
                if(flag==OP[i])
                {
                        flag=1;
                        break;
                }
        }
        return flag;
}

char Precede(char a,char b)//比较两个运算符的优先级
{
        char z;
        if((b=='+')||(b=='-')||(b=='*')||(b=='/')||(b=='(')||(b==')')||(b=='='))
                switch(a)
        {
                case '+':
                case '-':
                        if((b=='*')||(b=='/')||(b=='('))
                                z='<';
                case '*':
                case '/':
                        if(b=='(')
                                z='<';
                        else
                                z='>';
                        break;
                case '(':
                        if(b=='=')
                                z='E';
                        else if(b==')')
                                z='=';
                        else
                                z='<';
                        break;
                case ')':
                        if(b=='(')
                                z='E';
                        else
                                z='>';
                        break;
                case '=':
                        if(b=='=')
                                z='=';
                        else if(b==')')
                                z='E';
                        else
                                z='>';
                        break;
        }
        else z='E';
        return z;
}

DataType Operate(DataType a,char theta,DataType b)
{
        DataType z;
        switch((char)theta)
        {
        case '+':z=a+b;
                break;
        case '-':
                z=a-b;
                break;
        case '*':
                z=a*b;
                break;
        case '/':
                z=a/b;
                break;
        }
        return z;
}
double CaculateExpression(char *ptr)//计算表达式
{
        SqStack optr,opnd;
        DataType a,b,theta,x;
        char *p;
        double sum;
        int count;
        p=ptr;
        InitStack(optr);Push(optr,'=');
        InitStack(opnd);       


        while(*p!='='||GetTop(optr)!='=')
        {
                if(!In(*p))
                {
                        sum=0;
                        count=0;

                        while(*p>='0'&&*p<='9'||*p=='.')
                        {
                                if(*p!='.')
                                        sum=sum*10+*p-'0';
                                if(*p=='.'||count>0)
                                        count++;
                                p++;
                        }
                        if(count>0)
                                sum=sum/pow(10,count-1);//操作数为多位实数
                        Push(opnd,sum);
                }
                else
                        switch(Precede((char)GetTop(optr),*p))
                {
                        case '<':
                                Push(optr,*p);
                                p++;
                                break;
                        case '=':
                                Pop(optr,x);
                                p++;
                                break;
                        case '>':
                                Pop(optr,theta);
                                Pop(opnd,b);Pop(opnd,a);
                                Push(opnd,Operate(a,(char)theta,b));
                                break;
                        case 'E':
                                printf("表达式中括号不匹配!");
                                exit(1);
                }
        }
        return GetTop(opnd);
}

int main()
{
        char str[80];
        printf("Input a expression:\n");
        scanf("%s",str);
        printf("%f\n",CaculateExpression(str));
        return 0;
}

问：不知道为啥我这代码有什么问题，用vc++能编译运行，但每次输完表达式程序就不执行了，不知道我这代码错误在哪，望大佬能指出问题所在，十分感谢！

巴巴鲁

看着像是optr和opnd没有初始化

1298150336

巴巴鲁 发表于 2020-11-10 20:22
看着像是optr和opnd没有初始化

我在CaculateExpression函数里调用了InitStack()初始化了optr和opnd

lovedai

调试一下，看看你的调用越界了没，提问可以贴上你的错误和调试结果，看你说的让人很懵