数据结构实验2《基于栈的中缀算术表达式求值》

  • Post author:
  • Post category:其他


(visual studio 2019可运行)

输入及输出要求见《数据结构C语言(第二版)》严蔚敏版

【本文仅用于啥都看不懂还想交作业选手】

#include <iostream>
#include <stdlib.h>
#include <cstring>
#include<iomanip>//该头文件为了后面的输出保留两位小数
#define MAXSIZE 100//初始分配的存储空间
#define OK 1
#define OVERFLOW -2
#define ERROR -1
using namespace std;

//定义字符栈
typedef struct {
    char* base;
    char* top;
    int stackSize;
} SqStackOPTR;

//定义数字栈
typedef struct {
    double* base;
    double* top;
    int stackSize;
} SqStackOPND;

//字符栈的初始化
int InitStack(SqStackOPTR& S) {
    S.base = new char[MAXSIZE];
    if (!S.base) 
        exit(OVERFLOW);
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

//数字栈的初始化
int InitStack(SqStackOPND& S) {
    S.base = new double[MAXSIZE];
    if (!S.base) 
        exit(OVERFLOW);
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

//字符栈入栈操作
int Push(SqStackOPTR& S, char e) {
    if (S.top - S.base == MAXSIZE)
        return ERROR;
    *S.top++ = e;//元素e进栈
    return OK;
}

//数字栈入栈操作
int  Push(SqStackOPND& S, double e) {
    if (S.top - S.base == MAXSIZE) //说明栈满
        return ERROR;
    *S.top++ = e;//元素e进栈
    return OK;
}

//字符栈出栈操作
char Pop(SqStackOPTR& S) {
    char e;
    if (S.top == S.base)
        return ERROR;
    e = *--S.top;
    return e;
}

//数字栈出栈操作
double Pop(SqStackOPND& S) {
    double e;
    if (S.top == S.base) 
        return ERROR;
    e = *--S.top;
    return e;
}

//取字符栈栈顶元素
char GetTop(SqStackOPTR S) {
    char e;
    if (S.top == S.base) 
        return ERROR;
    e = *(S.top - 1);
    return e;
}

//取数字栈栈顶元素
double GetTop(SqStackOPND S) {
    double e;
    if (S.top == S.base) 
        return ERROR;
    e = *(S.top - 1);
    return e;
}

//判断输入的字符是数字还是运算符
int In(char ch)
{
    int isNumber;
    switch (ch) 
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case '(':
    case ')':
    case '=': isNumber = 1; break;
    default:  isNumber = 0; break;
    }
    return isNumber;
}

//定义一个判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
char Precede(char top, char ch) {//top为栈顶元素,ch为读入的字符
    char sym;
    switch (top) 
    {
    case '+':
    case '-':
        switch (ch)
        {
        case '+':
        case '-':
        case ')':
        case '=': sym = '>'; break;
        case '*':
        case '/':
        case '(': sym = '<'; break;
        } break;

    case '*':
    case '/':
        switch (ch)
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case ')':
        case '=': sym = '>'; break;
        case '(': sym = '<'; break;
        }break;
    case '(':
        switch (ch) 
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':sym = '<'; break;
        case ')': sym = '='; break;
        }break;
    case ')':
        switch (ch)
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case ')':
        case '=':sym = '>'; break;
        }break;
    case '=':
        switch (ch) 
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':sym = '<'; break;
        case '=':  sym = '='; break;
        } break;
    }
    return sym;
}

//定义运算的方法
double Operate(double a, char top, double b) {
    double sum = 0;
    switch (top) {
    case '+': sum = a + b;  break;
    case '-':sum = a - b; break;
    case '*': sum = a * b; break;
    case '/':sum = a / b; break;
    }
    return sum;
}

double EvaluateExpression(char ch) {
    SqStackOPTR OPTR;
    SqStackOPND OPND;
    InitStack(OPTR);
    InitStack(OPND);
    Push(OPTR, '=');//将表达式起始符’=‘压入OPTR栈
    char chs[20];//定义一个字符数组,来实现数字转换为字符串
    memset(chs, '#', sizeof(char) * 20);//将字符数组的元素设置为‘#’,即初始化chs数组,不然会报错

    while (ch != '=' || GetTop(OPTR) != '=') {//表达式没有扫描完毕或OPTR的栈顶元素不为“=”
        if (!In(ch)) {
            //这里应该将字符串转换为数字
            for (int i = 0; i < strlen(chs); i++) {
                if (chs[i] == '#' && !In(ch)) {
                    chs[i] = ch;
                    cin >> ch;
                }
                else {//如果数组的第i个元素为‘#’
                    break;
                }
            }
            double d = atof(chs);//把字符串转换成浮点数 double
            Push(OPND, d);
            memset(chs, '#', sizeof(char) * 20);//将字符数组的元素设置为‘#’
        }
        else {
            switch (Precede(GetTop(OPTR), ch)) {
            case '<':
                Push(OPTR, ch); cin >> ch;
                break;
            case '>':
                char theta;
                double b;
                double a;
                theta = Pop(OPTR);
                b = Pop(OPND);
                a = Pop(OPND);
                double sum;
                sum = Operate(a, theta, b);
                Push(OPND, sum);
                break;
            case '=':
                Pop(OPTR);
                cin >> ch;
                break;
            }
        }
    }
    return GetTop(OPND);
}

int main() {
    double res[MAXSIZE];//储存结果
    char ch;
    int i=0, j=0;
    while (1) 
    {    
        cin >> ch;
        if (ch == '=')
            break;
        else
        {
         res[i] = EvaluateExpression(ch);
         i++;
        }
    }
    for (j; j < i; j++)
    {
        cout << fixed << setprecision(2) << res[j]<< endl;
    }
   
    return 0;
}

(我现在的实力不允许我把它改成C语言,呜呜呜)



版权声明:本文为Madelena原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。