【实验目的】

使学生深入了解栈的特性，以便在实际问题背景下灵活运用栈，同时还将巩固对这种结构的构造方法的掌握及基本操作的实现。

【实验内容】

问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型的例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。
基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
测试数据：教科书例3-1的算术表达式3*(7-2),以及下列表达式：
8；1+2+3+4；88-15；1024/48；(20+2)(6/2)；3-3-3；8/(9-9)；2(6+2*(3+6*(6+6)))；(((6+6)*6+3)*2+6)*2。
实现提示：　　
（１）、采用优先级法，设置运算符栈和运算数栈，先将表达式转换成后缀表示，然后求值。
（２）、在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。
（３）、在识别出运算数的同时，要将其字符序列形式转换成整数形式。
（４）、在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。

【实验代码】

#include <iostream>

using namespace std;

template<class T>
struct StackNode //栈结点
{
    T data;
    StackNode<T> *next;
};

template<class T>
struct LinkStack // 链栈
{
    StackNode<T> *top;
    int count;
};

int priority[7][7] = {
        {1,  1,  -1, -1, -1, 1,  1},
        {1,  1,  -1, -1, -1, 1,  1},
        {1,  1,  1,  1,  -1, 1,  1},
        {1,  1,  1,  1,  -1, 1,  1},
        {-1, -1, -1, -1, -1, 0,  -2},
        {1,  1,  1,  1,  -2, 1,  1},
        {-1, -1, -1, -1, -1, -2, 0}
};    //优先级关系


template<class T>
bool InitStack(LinkStack<T> *s); // 初始化栈

template<class T>
bool push(LinkStack<T> *s, T data); // 入栈

template<class T>
bool pop(LinkStack<T> *s); // 出栈

template<class T>
bool StackEmpty(LinkStack<T> *s); // 判断栈是否为空

template<class T>
T GetTop(LinkStack<T> *s); // 返回栈顶元素

int GetPriority(char a, char b); // 运算符优先级比较
int Operate(int a, char theta, int b); // 运算

template<class T1, class T2>
void GetExpressionValue(LinkStack<T1> *OPNd, LinkStack<T2> *OPTr); // 总计算函数

int main() {

    LinkStack<int> *OPNd = new LinkStack<int>;
    LinkStack<char> *OPTr = new LinkStack<char>;
    InitStack(OPNd); // 初始化空栈
    InitStack(OPTr); // 初始化空栈

    push(OPTr, '#'); // 预先压入一个#，为了与表达式最后的#匹配
    cout << "请输入你要计算的表达式，记得在表达式的末尾加上'#'! " << endl;
    GetExpressionValue(OPNd, OPTr); // 开始计算
    cout << "答案为：" << GetTop(OPNd); // 输出运算结果
    return 0;
}

template<class T>
bool InitStack(LinkStack<T> *s) // 初始化栈
{
    //s->top = new StackNode<T>;
    s->top = NULL;
    s->count = 0;
    return true;
}

template<class T>
bool push(LinkStack<T> *s, T data) // 入栈
{
    StackNode<T> *p = new StackNode<T>;
    p->data = data;
    p->next = s->top;
    s->top = p;
    s->count++;
    return true;
}

template<class T>
bool pop(LinkStack<T> *s) // 出栈
{
    if (StackEmpty(s)) {
        cout << "栈为空，无元素可弹出！" << endl;
        return false;
    }
    StackNode<T> *p = s->top;
    s->top = p->next;
    s->count--;
    delete p;
    return true;
}

template<class T>
bool StackEmpty(LinkStack<T> *s) // 判断栈是否为空
{
    return s->top == NULL;
}

template<class T>
T GetTop(LinkStack<T> *s) // 返回栈顶元素
{
    if (s->top == NULL) {
        cout << "栈为空，无栈顶元素！" << endl;
    }
    return s->top->data;
}

template<class T1, class T2>
void GetExpressionValue(LinkStack<T1> *OPNd, LinkStack<T2> *OPTr) {
    char theta; // 记录运算符
    char ch; // 记录每次输入的字符

    cin >> ch; //载入第一个字符
    while (ch != '#' || GetTop(OPTr) != '#') {

        if (isdigit(ch)) {
            int data = 0;
            while (isdigit(ch)) {
                data = data * 10 + ch - '0';
                cin >> ch;
            }

            push(OPNd, data); // 将最新的数字压入栈中
        } else {

            switch (GetPriority(GetTop(OPTr), ch)) {
                case -1: // 栈顶运算符优先级小于新运算符
                {
                    push(OPTr, ch);
                    cin >> ch;
                    break;
                }
                case 0: // 栈顶运算符优先级等于新运算符，只有两种情况，（）和##，##不会出现，所以只会是（），所以只需弹出左括号即可
                {
                    pop(OPTr);
                    cin >> ch;
                    break;
                }
                case 1: // 栈顶运算符优先级大于新运算符，开始计算
                {
                    int a, b;
                    theta = GetTop(OPTr); // 获取栈顶运算符
                    pop(OPTr);
                    b = GetTop(OPNd); // 获取此时栈顶第一号数据
                    pop(OPNd);
                    a = GetTop(OPNd); // 获取此时栈顶第二号数据
                    pop(OPNd);
                    push(OPNd, Operate(a, theta, b)); // 将运算结果压入栈中
                    break;
                }
                default:
                    break;
            }
        }
    }
}

int GetPriority(char a, char b) // 运算符优先级比较
{
    int i = -1;
    int j = -1;
    switch (a) {
        case '#':
            i = 6;
            break;
        case ')':
            i = 5;
            break;
        case '(':
            i = 4;
            break;
        case '/':
            i = 3;
            break;
        case '*':
            i = 2;
            break;
        case '-':
            i = 1;
            break;
        case '+':
            i = 0;
            break;
        default:
            break;
    }

    switch (b) {
        case '#':
            j = 6;
            break;
        case ')':
            j = 5;
            break;
        case '(':
            j = 4;
            break;
        case '/':
            j = 3;
            break;
        case '*':
            j = 2;
            break;
        case '-':
            j = 1;
            break;
        case '+':
            j = 0;
            break;
        default:
            break;
    }

    if (i >= 0 && j >= 0) {
        return priority[i][j];
    } else {
        return -2;
    }
}

int Operate(int a, char theta, int b) // 运算
{
    int res = 0;
    switch (theta) {
        case '+':
            res = a + b;
            break;
        case '-':
            res = a - b;
            break;
        case '*':
            res = a * b;
            break;
        case '/':
            if (b == 0) {
                cout << "分母为零，运算出错！" << endl;
                res = 0;
            } else {
                res = a / b;
            }
            break;
        default:
            break;
    }
    return res;
}