DHU35 顺序栈ADT模板简单应用算法设计：应用中缀式进行二元表达式四则运算

问题描述 :

目的：使用C++模板设计顺序栈的抽象数据类型（ADT）。并在此基础上，使用顺序栈ADT的基本操作，设计并实现简单应用的算法设计。

内容：（1）请参照顺序表的ADT模板，设计顺序栈的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都聚焦在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的顺序表ADT原型文件，自行设计顺序栈的ADT。）

（2）ADT的简单应用：使用该ADT设计并实现若干应用顺序栈的算法设计。

应用11：在计算机中，对二元表达式可以有三种不同的标识方法: 前缀式、中缀式、后缀式。中缀式是人最习惯的使用方式。要求设计一个算法，使用顺序栈，设计并实现完成如下功能的算法：对于输入的任意一个中缀表达式，对其进行计算，并输入计算结果。

参考函数原型：

template<class ElemType1, class ElemType2>

double calc_inffix( SqStack<ElemType1> &OPND, SqStack<ElemType2> &OPTR, string &inffix );

//infix：中缀表达式字符串；OPND：操作数栈；OPTR：运算符栈

注意：设定表达式为合法表达式，且表达式的中间允许存在空格。其操作数的数据类型为int（允许多位数）。计算结果的数据类型为double。

输入说明 :

第一行：中缀表达式字符串

输出说明 :

第一行：去空格后的中缀表达式字符串

第二行：空行

第三行：计算结果

（中间有个空行）

输入范例 :

10+(2 0+(3(40-3)))5
输出范例 :

10+(20+(3(40-3)))5

665

#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;

template<class ElemType1, class ElemType2>
double calc_inffix(stack<ElemType1>& OPND, stack<ElemType2>& OPTR, string& inffix)
{
    map<char, double>mp;
    mp[ + ] = 2;mp[ - ] = 2;mp[ * ] = 3;mp[ / ] = 3;mp[ ( ] = 1;mp[ ) ] = 4;
    bool same_data = false;
    int i;
    for (i = 0;i < inffix.length();i++)
    {
        if (inffix[i] ==    )
        {
            inffix=inffix.erase(i,1);
            i--;
        }
    }
    cout << inffix << endl<<endl;
    for (i = 0;i < inffix.length();i++)
    {
        if (inffix[i] <=  9  && inffix[i] >=  0 )
        {
            if (same_data)
            {
                double data = OPND.top();
                OPND.pop();
                data = data * 10 + (double)(inffix[i] -  0 );
                OPND.push(data);
            }
            else
            {
                double data = (double)(inffix[i] -  0 );
                OPND.push(data);
                same_data = true;
            }
        }
        else 
        {
            same_data = false;
            if (OPTR.empty())
            {
                OPTR.push(inffix[i]);
            }
            else
            {
                if (mp[OPTR.top()] >= mp[inffix[i]])
                {
                    if (inffix[i] ==  ( )
                    {
                        OPTR.push( ( );
                        continue;
                    }
                    double data, a, b;
                    char ch = OPTR.top();
                    OPTR.pop();
                    OPTR.push(inffix[i]);
                    b = OPND.top();
                    OPND.pop();
                    a = OPND.top();
                    OPND.pop();
                    switch (ch)
                    {
                    case  + :data = a + b;break;
                    case  - :data = a - b;break;
                    case  * :data = a * b;break;
                    case  / :data = a / b;break;
                    }
                    OPND.push(data);
                }
                else
                {
                    if (inffix[i] ==  ) )
                    {
                        while (OPTR.top() !=  ( )
                        {
                            double data, a, b;
                            char ch = OPTR.top();
                            OPTR.pop();
                            b = OPND.top();
                            OPND.pop();
                            a = OPND.top();
                            OPND.pop();
                            switch (ch)
                            {
                            case  + :data = a + b;break;
                            case  - :data = a - b;break;
                            case  * :data = a * b;break;
                            case  / :data = a / b;break;
                            }
                            OPND.push(data);
                        }
                        OPTR.pop();
                    }
                    else OPTR.push(inffix[i]);
                }
            }
        }
    }
    while (!OPTR.empty())
    {
        double data, a, b;
        char ch = OPTR.top();
        OPTR.pop();
        b = OPND.top();
        OPND.pop();
        a = OPND.top();
        OPND.pop();
        switch (ch)
        {
        case  + :data = a + b;break;
        case  - :data = a - b;break;
        case  * :data = a * b;break;
        case  / :data = a / b;break;
        }
        OPND.push(data);
    }
    return OPND.top();
}

int main()
{
    stack<double> OPND;
    stack<char> OPTR;
    string inffix;
    getline(cin, inffix);
    cout << calc_inffix(OPND, OPTR, inffix) << endl;
    return 0;
}