算术表达式求值演示-严蔚敏版数据结构课设

后缀表达式应用

实现代码：

```cpp
#include <iostream>
#include <malloc.h>
#include <cstring>
#include <iomanip>
#include <math.h>
using namespace std;
#define STACK_INIT_SIZE 100  //存储空间初始分配量
#define STACK_INCREMENT_SIZE 20 //存储空间增量
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1

typedef int  Status;

typedef struct node{
    double num;//数字
    char op;//操作符
    bool flag;//判断是数字还是操作符，1为数字
}node;
typedef node ElemType;

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(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status StackEmpty(SqStack S){
    //判断栈是否为空
    if(S.base == S.top) return TRUE;
    else return FALSE;
}
Status ClearStack(SqStack &S)
{ // 把S置为空栈
   S.top=S.base;
   return OK;
}
ElemType GetTop(SqStack S){
    //用e返回栈顶元素
    if(StackEmpty(S)) exit (ERROR);
    return *(S.top-1);
}

Status Push(SqStack &S,ElemType e){
    //将e压入栈
    if(S.top - S.base >= S.stacksize) {
        //栈满，增加分配空间
        S.base = (ElemType *) realloc (S.base , (S.stacksize+STACK_INCREMENT_SIZE) * sizeof(ElemType));
        if(!S.base) exit(OVERFLOW); //分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT_SIZE;
    }
    * S.top++ = e;
    return OK;
}
Status Pop(SqStack &S) {
    //将栈顶元素出栈
    if(S.base == S.top) return ERROR;
    --S.top;
    return OK;
}

Status StackTraverse(SqStack S)
 { //
   if(S.top==S.base) {
     cout<<"这里什么也没有！"<<endl;
     return ERROR;
   }
   ElemType * p;
   p=S.base;
   while(p<S.top)
     {
         if((*p).flag==0){
             cout<<(*p).op<<' ';
         }
         else cout<<(*p).num<<' ';

         p++;
     }
   cout<<endl;
   return OK;
 }


Status isNumber(char ch){
    if(ch >='0' && ch<= '9') return TRUE;
    else return FALSE;
}

int Precede(char c){
    if (c <= '9' && c >= '0')
        return 5;
    else if (c <= 'z' && c >= 'a')
        return 6;
    else if (c <= 'Z' && c >= 'A')
        return 6;
    else if (c == '.')
        return 7;
    else {
        switch (c) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '(':
                return 4;
            case ')':
                return 3;
            default:
                return 0;
        }
    }
}

Status TansPost(SqStack &PostStack,SqStack & Op,string cs){
    double num=0;//暂时存储小数部分值
    ElemType temp;
    int i=0;
    if(cs[i]=='-'){//表达式首位为'-'情况,先在后缀表达式前添加零，达到实现负数目的
        temp.flag=true;
        temp.num=0;
        Push(PostStack,temp);
    }
    while(i<cs.length()){
        if(cs[i]==')'){
            while(!StackEmpty(Op)&& GetTop(Op).op!='('){
                Push(PostStack,GetTop(Op));
                Pop(Op);
            }
            Pop(Op);//弹出左括号
            i++;

        }

        else if(cs[i]=='('){
            temp.flag =false;
            temp.op=cs[i];
            Push(Op,temp);
            i++;
            if(cs[i]=='-'&&isNumber(cs[i+1])){//得到负数
                temp.flag=true;
                temp.num=cs[++i]-'0';i++;
                while(i<cs.length() && isNumber(cs[i])){
                    temp.num = temp.num *10 +(cs[i]-'0');
                    i++;
                }//整数部分计算完成

                if(cs[i]=='.'){
                    i++;
                    double j=1;
                    while(i<cs.length() && isNumber(cs[i])){
                    num += pow(0.1,j) * (cs[i]-'0');
                    i++;j++;
                    }
                }
                temp.num +=num;
                num=0;//下一次继续使用
                temp.num=0-temp.num;
                Push(PostStack,temp);
                }

        }

        else if(isNumber(cs[i])){
            temp.flag=true;
            temp.num=cs[i++]-'0';
            while(i<cs.length() && isNumber(cs[i])){
                temp.num = temp.num *10 +(cs[i]-'0');
                i++;
            }//整数部分计算完成

            if(cs[i]=='.'){
                i++;
                double j=1;
                while(i<cs.length() && isNumber(cs[i])){
                    num += pow(0.1,j) * (cs[i]-'0');
                    i++;j++;
                }
            }
            temp.num +=num;
            num=0;//下一次继续使用
            Push(PostStack,temp);

        }

        else {//需要增加一个条件是不不能够遇上左括号
            temp.flag =false;
            while(!StackEmpty(Op) && GetTop(Op).op!='(' &&
                                    Precede(cs[i])<=Precede(GetTop(Op).op)){
                Push(PostStack,GetTop(Op));
                Pop(Op);
            }
            temp.op=cs[i];
            Push(Op,temp);
            ++i;

        }
    }

    while(!StackEmpty(Op)){//将Op栈全部压入后缀表达式逆序
        Push(PostStack,GetTop(Op));
        Pop(Op);

    }
    cout<<"后缀表达式：";
    StackTraverse(PostStack);
}

double Calculate(SqStack & PostStack_temp,SqStack & Op){//此时Op作为辅助后缀表达式的计算栈
    double temp1,temp2;
    node cur ,temp;
    SqStack PostStack;InitStack(PostStack);

    while(!StackEmpty(PostStack_temp)){//逆序才是后缀表达式
        Push(PostStack,GetTop(PostStack_temp));
        Pop(PostStack_temp);
    }

    while(!StackEmpty(PostStack)){
        cur =GetTop(PostStack);
        Pop(PostStack);
        if(cur.flag == true) Push(Op,cur);
        else {
            temp2 = GetTop(Op).num;
            Pop(Op);
            temp1 = GetTop(Op).num;
            Pop(Op);
            temp.flag = true;
            if     (cur.op == '+') temp.num = temp1 + temp2;
            else if(cur.op == '-') temp.num = temp1 - temp2;
            else if(cur.op == '*') temp.num = temp1 * temp2;
            else                   temp.num = temp1 / temp2;

            Push(Op,temp);
        }
    }
        return GetTop(Op).num;
}

int main(){
    string cs;
    SqStack PostStack,Op;
    InitStack(PostStack); InitStack(Op);
    while(1){
        cout<<"请输入要计算的表达式：";
        cin>>cs;cout<<endl;
        TansPost(PostStack,Op,cs);
        cout<<'\n';
        cout<<"计算结果：";
        cout<<cs<<" = ";
        cout<<fixed<<setprecision(2)<<Calculate(PostStack,Op)<<'\n'<<endl;
        cs.erase(0);ClearStack(PostStack);ClearStack(Op); //清空字符串和两个栈，便于循环计算
        cout<<'\n'<<'\n'<<'\n';
    }
        return 0;
}