• 实验目的和要求

熟悉并使用顺序栈。

1. 要求计算方法根据PPT例题求解方法进行。
2. 只处理整型算术运算表达式，即运算符至少包含+-*/()。
3. 其中，要求抽象出栈结构进行独立实现。
4. 其它要求同课后作业-01要求。

二、实验环境

硬件环境：微型计算机

操作系统：Windows 11

语言：C++
软件环境：IDEA Microsoft Visual Studio 2019   

三、实验内容

设计并实现一个整型表达式计算器，只处理整型算术运算表达式，即运算符至少包含+-*/()，其中，要求抽象出栈结构进行独立实现。

四、实验过程

4.1 任务定义和问题分析

         需要实现整型算术表达式的运算，运用抽象栈的结构。

    需要考虑表达式的输入和使用，以及元素类型转换的问题。

    需要考虑运算符优先级设置的问题。

    需要判断栈当前的状态，并返回相应的结果。

4.2 概要设计（数据结构）

 

1. 读入整形表达式并对其中的元素进行拆分

本次实验的数据采用键入的方式，将键入的数据存入string类中，string类不必担心内存是否足够、键入字符串长度，而且作为一个类出现，他集成的操作函数足以完成大多数情况下的需要，它可以看成是C++的基本数据类型。所以在头文件加入<string>，用类自带的.size()函数得到输入表达式的长度。string定义的类型可以直接使用下标操作符[]像数组一样被调用，方便了元素性质的判断和类型的转换。

1. 判断元素的类型

本次实验通过isp()和isr()两个函数，比较元素的ASCII码实现元素类型的判断。

1. 栈的设计和应用

(1)几个运算的条件可能有不成立的情况，因此，需要给予明确的反映。

(2)设立运算是否正常的类型errorcode，正常时返回success, 否则返回错误类型，如overflow, underflow等。enum errorcode {success, overflow, underflow}; 可以将这几个函数的类型设置为errorcode;。

(3)如果需要返回其他的值，可以作为参数来返回。

(4)取栈顶元素的运算功能描述: 如果栈不空，则取出栈顶元素到参数x中，然后返回success。否则，返回downflow。 对应的运算函数为:errorcode get_top(elementtype &x) const。

(5)入栈的运算功能描述: 如果栈不满，则将元素入栈，并返回success。 否则，返回overflow。对应的运算函数为:errorcode push(const elementtype x)。

(6)出栈的运算功能描述: 如果栈不空，删除当前栈顶的元素，并返回success。 否则，返回underflow。对应的运算函数为:errorcode pop()。

(7)使用模板类，拓宽类的适用范围，减少程序冗余，是代码具有高效性。

1. 操作符优先级的设置和比较及其运算

(1)在整个算数表达式的前后加上“#”，作为优先级最低的运算符，等级为-1，方便与其他运算符入栈和出栈的比较。

(2)赋予不同的运算符不同的等级，其中“（”、“）”等级为0，“+”、“-”等级为1，“*”、“/”等级为2。

(3)进入判断程序比较与栈顶的运算符的优先级，同时判断是否是左右括号，左右括号是否见面。

(4)达到计算要求后取出栈顶的数据，并将栈顶下移一层，再次去除栈顶的数据，依据运算符号进行相应的运算。

4.3 详细设计

 实现数据类型的判断

 

 实现最后数据的计算

 

 数据类型转换

 

 对于操作数的操作

 

 

对于运算符的操作

 

栈的实现

五、测试及结果分析

5.1 实验数据

         1+1

         (1+1)

34+26*18-66/3

37+4*(2+3*17-21/3)*6-(4+8)*12

9*(12*5-4/2)*(33-36/9)+10/5-14*(3*8/6)

5.2 结果及分析

                           1+1=2

 

                             

                                 （1+1）=2

 

                             

                                 34+26*18-66/3=480

 

                             

                 

 

37+4*(2+3*17-21/3)*6-(4+8)*12=997

                             

                             

 

                                                     9*(12*5-4/2)*(33-36/9)+10/5-14*(3*8/6)=15084

六、实验收获

         1. 一个编译器用不下去的时候要学会换一个，VS的界面显然更好看一点。

         2. 当运算结果挑战了你的数学认知的时候千万不要怀疑，那绝对不会是数学的问题。

         3. 在开始编写程序之前要做好流程给的设计，理清逻辑关系，在实际编程中才不会把任务和数据混淆。

         4. 不要在一条路上走到黑，必要的搜索和思路调整也许能把程序拖出困境。

         5. 时刻注意数组的下标！

七、参考文献

         一些CSDN的文章😊

八、附录（源代码）

#include <iostream>
#include <stack>
#include <string>
using namespace std; 
enum errorcode {
    success, overflow, underflow
};
template<class T>
class Stack {
public:
    Stack() {
        count = 0;
    }
    bool empty()const {
        if (count == 0) return true;
        else return false;
    }
    bool full()const {
        if (count == 50) return true;
        else return false;
    }
    template<class T>
    errorcode get_top(T& x)const {
        if (empty()) return underflow;
        else {
            x = data[count - 1];
            return success;
        }
    }
    template<class T>
    errorcode push(const T x) {
        if (full()) return overflow;
        data[count] = x;
        count++;
        return success;
    }
    errorcode pop() {
        if (empty()) return underflow;
        count--;
        return success;
    }
private:
    int count;
    T data[50];
};

bool isp(char n) {
    if (n >= '0' && n <= '9') return 1;
    return 0;
}

int isr(char n) {
    if (n == '+' || n == '-')
        return 1;
    else if (n == '*' || n == '/')
        return 2;
    else if (n == '(' || n == ')')
        return 0;
    else
        return -1;
}

int jisuan(char x, Stack<int>& num) {
    int a, b;
    int c = 0;
    if (x == '+') {
        num.get_top(a);
        num.pop();
        num.get_top(b);
        num.pop();
        c = a + b;
    }
    else if (x == '-') {
        num.get_top(a);
        num.pop();
        num.get_top(b);
        num.pop();
        c = b - a;
    }
    else if (x == '*') {
        num.get_top(a);
        num.pop();
        num.get_top(b);
        num.pop();
        c = a * b;
    }
    else if (x == '/') {
        num.get_top(a);
        num.pop();
        num.get_top(b);
        num.pop();
        c = b / a;
    }
    return c;
}

int change(char x) {
    int y;
    y = x - 48;
    return y;
}

int Panduan(string a) {
    Stack<int> s1;
    Stack<char> s2;
    a += '#';
    s2.push('#');
    for (int i = 0; i <= a.size(); i++) {
        if (isp(a[i])) {
            int sum = change(a[i]);
            while (isp(a[i+1])) {
                i++;
                sum = sum * 10 + change(a[i]);
            }
            s1.push(sum);
        }
        else {
            int k = 1;
            char x, y;
            s2.get_top(x);
            while (k) {
                if (isr(a[i]) > isr(x) || a[i] == '(') {
                    s2.push(a[i]);
                    break;
                }
                else {
                    if (isr(a[i]) == isr(x) && isr(a[i]) == 0 || isr(a[i]) == isr(x) && isr(a[i]) == -1) {
                        s2.pop();
                        break;
                    }
                    else {
                        s1.push(jisuan(x, s1));
                        s2.pop();
                        s2.get_top(y);
                        x = y;
                    }
                }
            }
        }
    }
    int p;
    s1.get_top(p);
    return p;
}

int main() {
    string a;
    cin >> a;
    cout << Panduan(a) << endl;
    return 0;
}