用顺序栈实现表达式求值,请xdm指正逻辑错误


#include<iostream>
using namespace std;
#include<stdlib.h>
#define MAXSIZE 100

typedef struct
{
    char *base,*top;
    int stacksize;
 }SqStack;
 
int InitStack(SqStack &S)
{
    S.base=new char[MAXSIZE];
    if(!S.base)
        exit(0);//存储分配失败 
    S.top=S.base;//top初始为base,空栈 
    S.stacksize=MAXSIZE;
    return 1;
        
}

char GetTop(SqStack S)
{
    if(S.top!=S.base)
        return *(S.top-1);//返回栈顶元素的值,栈顶指针不变 
 } 

int Push(SqStack &S,char e)
{
    if(S.stacksize==S.top-S.base)
        return 0;//栈满 
    *S.top++=e;
    return 1;
 } 
 
int Pop(SqStack &S,char &e)
{
    if(S.top==S.base)
        return 0;//栈空 
    e=*--S.top;
    return 1;
}

bool In(char ch)//判断读入的字符ch是否为运算符 
{
    if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
        return true;
    else
        return false;
}

char Precede(char i,char j)//判断运算符的栈顶元素与读入的运算符之间优先关系的函数 
{
    switch(i)
    {
        case'+':
        case'-':
            if(j=='*'||j=='/'||j=='(')
                return '<';
            else
                return '>';
            break;
        case'*':
        case'/':
            if(j=='(')
                return '<';
            else
                return '>';
            break;
        case'(':
            if(j==')')
                return '=';
            else
                return '<';
            break;
        case'#':
            if(j=='#')
                return '=';
            else
                return '<';
            break;
    }
 } 
 
char Operate(char a,char theta,char b)//二元运算 
{
    switch(theta)
    {
        case'+':
            return a+b;
            break;
        case'-':
            return a-b;
            break;
        case'*':
            return a*b;
            break;
        case'/':
            return a/b;
            break;
    }
 } 

char EvaluateExpression()
{
    SqStack OPTR,OPND;
    char ch,theta,a,b,x; 
    InitStack(OPTR);
    InitStack(OPND);
    Push(OPTR,'#'); 
    cout<<"请输入表达式(以#结束):";
    cin>>ch;
    cout<<"表达式的运算结果为:";
    while(ch!='#'||GetTop(OPTR)!='#')//表达式没有扫描完毕或OPTR的栈顶元素不为"#" 
    {
        if(!In(ch))
        {
            Push(OPND,ch);
            cin>>ch;
        }
        else
        {
            switch(Precede(GetTop(OPTR),ch))
            {
                case'<':
                    Push(OPTR,ch);
                    cin>>ch;
                    break;
                case'>':
                    Pop(OPTR,theta);//弹出OPTR栈顶的运算符 
                    Pop(OPND,b);
                    Pop(OPND,a);//弹出OPND栈顶的两个运算数 
                    Push(OPND,Operate(a,theta,b));
                    break;
                case'=':        //OPTR的栈顶元素是'('且ch是')' 
                    Pop(OPTR,x);
                    cin>>ch;
                    break;
            }
        }
        return GetTop(OPND);
    }    
}

int main()
{
    cout<<EvaluateExpression()<<endl;
    return 0;
 } 

img

我想知道你为什么不用std::stack