顺序栈ADT模板简单应用算法设计：应用中缀式进行二元表达式四则运算(期中考终于结束了，终于又能开始码了)

问题描述 :

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

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

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

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

参考函数原型：

template<class ElemType>

int 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

思路分析

关于中缀运算的基本知识点

问题分析

• 使用中缀表达式计算——数栈和符号栈进行交替输出
• 一个完整的数式由多个数字组成的，数字之间可以有空格，能有效去除空格识别数字

去除表达式中的所有的空格

• 扫描的时候，需要提前看到下一位，来决定当前位的操作

中缀表达式的计算

• 扫描整个的表达式，数字直接入数字栈，符号根据优先级进行调整

• 符号优先级调整规则：

  • 同类之间，先到一定优先级高
  • 不同类之间，先乘除后加减
  • 优先的一定优先计算，入栈了也出栈

• 可以使用数字表示不同符号之间的优先级

流程表

伪代码实现

• 用数字来表示优先级，同种类的用同样的数字，除了加减乘除都是0

int getPriority(char signal)
{
    switch (signal)
    {
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        default:
            return 0;
    }
}

• 比较两个运算符优先级，返回为1，说明，栈内的优先级高，返回0说明扫描的优先级高

/*
    description: return 1 the priority of InStack is smaller than the priority of OutStack
                 return 0 the priority of InStack is bigger than the priority of OutStack
*/

int compareOfSignal(char InStack , char OutStack)
{
    if(OutStack == '(')
    {
        return 1;
    }

    if(InStack == '(')
    {
        return 1;
    }

    if(getPriority(InStack) >= getPriority(OutStack))
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

• 实际计算两个对象的函数

// function: to calculate the result of two numbers
double calculate(char signal,double num1,double num2)
{
    switch (signal)
    {
        case '+':
            return num1+num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            return num1 / num2;
        default:
            return 0;
    }
}

• calc_inffix()

int calc_inffix(  SqStack<double> &OPND, SqStack<char> &OPTR, string &inffix )
{
    //处理字符串，将空格消除
    for(int j = 0;j < inffix.length();j ++)
    {
        if(inffix.at(j) == ' ')
        {
            inffix.erase(j,1);
        }
    }
 

    //扫描整个字符串，一个一个的分析情况
    while(i < inffix.length())
    {
		//遍历的字符是数字的处理
        if(inffix.at(i) >= '0' && inffix.at(i) <= '9')
        {
   			//长整数拼接的基本方法
            temp=temp * 10 + (inffix.at(i) - '0');
            //提前预读下一个字符，根据下一个字符判定是否将生成的数字压入栈中
            //注意：最后一个到达字符串的末尾
            if(i == inffix.length() -1  || (inffix.at(i+1) < '0' || inffix.at(i+1) > '9'))
            {
                OPND.push(temp);
                //不要忘记每次将临时存放拼接数字的容器清零
                temp = 0;
            }
            i ++;
        }
        //处理符号
        else
        {
        	//获取栈顶的符号，用于比较优先级
            OPTR.GetTop(inStack);
			
			//右括号不便比较优先级，将之单列出来，直接处理符号栈到左括号
            if(inffix.at(i) == ')')
            {
                do
                {
                    OPTR.pop(signalTemp);
                    OPND.pop(right);
                    OPND.pop(left);
                    //calculate根据传进来恶的符号值进行相关的计算
                    result = calculate(signalTemp,left,right);
                    OPND.push(result);
                    OPTR.GetTop(inStack);
                }while(inStack != '(');
                //最后注意：将左括号出栈，从而将整个括号清空
                OPTR.pop(signalTemp);
                i ++;
            }
            else if(compareOfSignal(inStack,inffix.at(i)))
            //compareOfSignal（A，B）比较A和B的优先级
            {
				//当前扫描的符号优先级高于符号栈栈顶的符号的优先级
                OPTR.push(inffix.at(i));
                i ++;
            }
            else
            {
            	//当前扫描的符号的优先级低于符号栈栈顶的符号的优先级
                do
                {
                	//注意：迭代的条件终止的条件：符号栈已经为空了，或者符号栈栈顶的运算符的优先级低于当前扫描的运算符
                    OPTR.pop(signalTemp);
                    OPND.pop(right);
                    OPND.pop(left);
                    result = calculate(signalTemp,left,right);
                    OPND.push(result);
                    OPTR.GetTop(inStack);
                }while(!OPTR.StackisEmpty() && !compareOfSignal(inStack,inffix.at(i)));
                
                //将之扫描的运算符入栈
                OPTR.push(inffix.at(i));
                i ++;
            }
        }
    }


    //已经扫描完毕，直接操作两个栈中的数据
    while(!OPTR.StackisEmpty())
    {
        OPTR.pop(signalTemp);
        OPND.pop(right);
        OPND.pop(left);
        result = calculate(signalTemp,left,right);
        OPND.push(result);
    }

    OPND.pop(result);
    return result;
}

事故现场

第一次提交

• 样例是通过了，这是显而易见的，应该是没有考虑到对小数的处理，仅仅是将数据变成整型进行保存的，所以将数据类型变成双精度型进行保存

第二次提交

• 仍旧没有通过，不仅仅是单纯的修改成浮点型，自己要去拟定几组浮点型的测试数据
• 1/2
  
• 忽然间明白了，我的计算函数，仍旧是接收整型数据计算的，并不是以浮点型数据计算的

• 返回类型，传入的参数都要修改成浮点型
• 修改之后运行，对了，符合浮点型了

第三次提交

• 写的有点久，就买一个样例吧
  
• 应该是程序运行的逻辑错了

第四次提交

• 着实优点无语了，但这次要自己写出来样例，自己找问题
• 当计算1+2/2*3时，现如无限的死循环
• 根本原因将同等级的优先级，先到的优先这句话理解错了，当输入1+1+1，读入到第二个加号时，第一个加号的结果已经出来了，不会等到最后都遍历完了再去想到计算两个加号的值

第四次提交

• 还是错的，自己在想一个例子，最好能组合不同的运算符和括号

• 测试了很多的样例：

  1+ 2 /（1+1）* 366 * 133-（4-3）* （ 5 - 6 ） 
  2*（1+2*（3/（3-1）））
  

• 于是乎又买了一个样例

• 这就很过分，明明规定的函数返回类型是整型，居然让我输出浮点型

绝对最后一次提交

分析与总结

关于OJ上ADT使用的注意事项

• 关于GetTop（Elem）查看栈顶数据的函数
  • 如果读取失败，不会改变Elem的值
  • 如果你重复利用一个Elem，就会保留上一次读入的值，会影响你的判断
  • 所以，要么每次使用完记得将该值重置为无意义，要么不适用同一个数值

关于该问题的一些注意事项

针对减法和除法的运算顺序问题

• 实际计算中，注意先弹出的是右操作数，在弹出左操作数，顺序不要弄错，对于减法和除法，是不满足交换律的，有顺序的。
• 所以，先弹出来的是减数或者是除数，后弹出来的是被除数或者是被减数

关于符号优先级的理解问题

• 同水平或者同类型的，如”加和减“”乘和除“，先进去的，优先级高，后进去的优先级低
• 1+2+3，扫描到第二个加号的时候，1+2已经计算出来了，并且入栈了。

关于C++编程的异常

不要将不需要用到ElemType的方法声明为模板类

• 如果你的函数中没有涉及到模板类，那就不需要声明为模板类，不然会出现找不到匹配函数的错误。

常用的删除字符串中空格的方法

• 删除字符串中的空格的方法

//deal with the string and output
for(int i= 0;i < inffix.length();i ++)
{
    if(inffix.at(i) == ' ')
    {
        inffix.erase(i,1);
    }
}
cout<<inffix<<endl;

个人总结

• 整体来说，是写出来，但是思路不够完善，代码不够简洁，太过混乱了。完成的方法也是先按照脑袋里的思路，用到什么方法，再去些什么方法，缺什么逻辑，再去补什么逻辑，这样的思路不够完善，不够流畅，很失败。
• 可以适当的参考一下老师的思路去改善自己的代码