栈的实际运用

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

使用栈来计算表达式

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

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

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

核心思路

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

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

优先关系

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

image-20210322200835566

  1. θ1 < θ2 θ1 优先级低于θ2
  2. θ12 θ1 优先级高于θ2
  3. θ12 θ1 优先级等于θ2

θ1 表示右运算符, θ2 表示左运算符

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

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

  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.

运行结果

image-20210322195130319

核心代码

#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;
}

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://yingwiki.top/2021/03/22/stack-apply2
最后更新于:  129  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟