栈的实际运用

上一篇，介绍了栈是如何判断括号匹配的问题，与之类似的，栈还可以求表达式

使用栈来计算表达式

我们一般再计算表达式的时候，会注意那些问题呢？

1. 优先级 先乘除 后加减
2. 从左到右
3. 先算括号里面的

栈的先进后出来描述，这里的优先级在合适不过了！！！。

核心思路

我们需准备两个栈 OPTR和OPND ，分别存储 运算符和操作数。

依次扫描表达式字符串，为数值进入 OPND ；运算符进入 OPTR

优先关系

为了描述运算符的优先级，我们构建如下关系表：

1. θ₁ < θ₂ θ₁ 优先级低于θ₂
2. θ₁ >θ₂ θ₁ 优先级高于θ₂
3. θ₁ =θ₂ θ₁ 优先级等于θ₂

θ₁ 表示右运算符， θ₂ 表示左运算符

上述关系表，完美概括了 优先级的关系。

首先这张关系表就构建的很秒

1. 从左到右 ：一般从我们人类的角度思考，计算从左到右，这一条往往是直接刻在我们潜意识里的，但是对于计算机来说，这一点得我们告诉ta。

   简单概括一下**，同一个运算符也分左右，右运算符大于左运算符（相对操作数左右而言）**。

2. 先计算括号里面的，后计算括号外面的，这一句，可以表示为 ，右运算符的右括号比任何运算符优先级都底，遇到左运算符的左括号优先级相等

   那么= 之时就是，去括号之时

3. 为了能够正确的结束表达式的运算，我们还需加入 # 作为休止符，当然他也成对，表达式开始一个，结尾一个。

4. 当然这个表空缺的地方 表示 表达式错误

充分理解了这一张构思精妙的表，才能有如下的算法。

运算符之间的pk

这里就使用栈的特点了，栈顶的元素是最先出去的，我们可以用此特性来表示，当前需要计算的运算符优先级最高，例如

#1+3*5 #

当扫描到* 时，栈内已经进入了 # + <--(top) ，发现＋没有 * 有限高，我们应该将 * 填入作为栈顶。

那么啥时候 做运算处理呢？，当然是新的操作符没有 就栈顶操作符高 的时候。 即为 >

对于优先级相等的情况，我们就是来判断括号里的运算是否计算完成,以及 计算是否结束。

这样，运算完成的操作符自动出栈，留下都是没有处理的，再次进行判断，这样，我们就把一个表达式拆分成多个关于两个操作数运算，最终，OPTR一定只有 #.

操作数的存储

栈为我们保存的操作数（由于先进后出的特点，栈顶元素一定是最先被运算的操作数），而我们都是进行的关于两个操作数运算，栈顶和栈顶的下一个数值，就是我们当前计算的的两个操作数。

当然值得注意的是，对于减法和除法需要分顺序的计算，需注意顺序。

如此下来，最后一个操作数就为结果。

算法描述

当然是伪代码啦

OperandType EvaluaEXpression()
{
    InitStack(OPTR);
    Push(OPTR);//作为开头标志
    InitStack(OPND); c=gatchar();
    while(c!=#||GetTop!=#)
    {
        if(In(c,op))//不是操作符进操作数栈
        {
        	Push(OPND,c);
            c=getchar();
        }
        else{
            switch(Precode(GetTop(OPTR),c))
            {
                case '<'://栈顶元素优先级比较低
                    Push(OPTR,c);
                    break;
                case '='://去括号
                    Pop(OPTR,x);
                    break;
                case '>':
                    Pop(OPTR,theta);
                    Pop(OPND,a);
                    Pop(OPND,b);
                    Push(OPND,Operator(b,theta,a));
                    break;
            }//switch
        }//else
	}//while
    return Getop(OPND);
}

代码

其实这个代码，我非常不满意，首先是，使用的c语言，没有string类型，难受，所以引入了c++的库。

我其实应该使用c++来编写会让我感受更清爽一些，模板类，可以把栈完美地封装。

当然，最让我难以接受的是，我使用的还是，前几天写的存储int类型的栈，导致我还需将int类型和字符类型还有一个映射关系。

外加，一边值班，一边写代码，导致我思路非常不连续，基本是想到啥写啥。QWQ

这里立一个flag，使用类重新写本算法。

当然这里还有许多错误情况没有考虑，没事那么多时间去完善了，QWQ.

运行结果

核心代码

#include"EvaluateExpression.h"
#include"Stack.h"
int IsOperator(char c)
{
	switch (c)
	{
	case '+':return 0; break;
	case '-':return 1; break;
	case '*':return 2; break;
	case '/':return 3; break;
	case '(':return 4; break;
	case ')':return 5; break;
	case '#':return 6; break;
	}
	return -1;
}
/* 运算符对照表 */
// >  <  =   $表示错误
const char Prior[7][7] = {
	{'>','>','<','<','<','>','>'},//+
	{'>','>','<','<','<','>','>'},//-
	{'>','>','>','>','<','>','>'},//*
	{'>','>','>','>','<','>','>'},// /
	{'<','<','<','<','<','=','$'},//(
	{'>','>','>','>','$','>','>'},//)
	{'<','<','<','<','<','$','='}// # 
	};

char OperatorPrior(int c1, int c2)
{
	return Prior[c1][c2];
}

int calculate(int num1, int c, int num2)
{
	switch (c)
	{
	case 0:return num1 + num2;break;
	case 1:return num1 - num2;break;
	case 2:return num1 * num2;break;
	case 3:return num1 / num2; break;
	}
	return 0;
}

int EvaluateExpression(std::string s)
{
	SqStack OPTR, OPND;
	if (!Init_SqStack(OPND) || !Init_SqStack(OPTR))
		exit(0);
	Push(OPTR, 6); //插入开始标志 方便判断计算是否完成
	s = s + '#'; //判读是否结束
	char c = s[0];
	int i = 1;
	int e,b,a;
	int tmp;
	GetTop(OPTR, e);
	while (c!='#'|| e!=6) {  //表达式未读完或者运算未完 
		int sum = 0;
		if (c >= '0' && c <= '9') {
			while (c >= '0' && c <= '9') {  //输入高位数
				sum = sum * 10 + (c - '0');
				c = s[i++];
			}
			Push(OPND,sum);  // 把读进的数字入数字栈 
		}
		else {
			tmp=IsOperator(c);
			switch (OperatorPrior(e, tmp))
			{
			case '<':  //栈顶元素优先权低 
				Push(OPTR, tmp);
				c = s[i++];
				break;
			case '=':
				Pop(OPTR,e);  // 脱括号 
				c = s[i++];  
				break;
			case '>':  //退栈并将运算结果入栈 
				Pop(OPTR, e);
				Pop(OPND, a);
				Pop(OPND, b);
				Push(OPND, calculate(b, e, a));
				break;
			}
		}
		GetTop(OPTR, e);//读取当前运算判断是否为 #
	}
	GetTop(OPND, e);
	return e;
}