数据结构:表达式求值

数据结构:表达式求值数据结构:表达式求值表达式求值是程序设计语言编译的一个最基本问题,其中任何一个表达式都是由操作数、运算符(±*/)、界限符(#,(,),[,])组成。运算符和界限符统称算符。算符的优先级关系为(数学角度上):为了通过代码实现,我们定义两个工作栈,一个叫OPTR,存运算符和界限符;另一个存OPND,存操作数或运算结果。首先OPND为空栈,OPTR首先存’#’为栈底元素。依次读取算术表达式…

大家好,又见面了,我是你们的朋友全栈君。

数据结构:表达式求值

表达式求值是程序设计语言编译的一个最基本问题,其中任何一个表达式都是由操作数、运算符(±*/)、界限符(#,(,),[,] )组成。运算符和界限符统称算符。算符的优先级关系为(数学角度上):
在这里插入图片描述
为了通过代码实现,我们定义两个工作栈,一个叫OPTR,存运算符和界限符;另一个存OPND,存操作数或运算结果。
首先OPND为空栈,OPTR首先存’#’为栈底元素。
依次读取算术表达式,如果是操作数,存OPND;如果是运算符或界限符,则和OPTR的栈顶元素比较优先级,如果优先级高,存入栈,如果优先级低,则进行运算操作。。。
在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100//存储空间初始分配量 
#define STACKINCREMENT 10//分配增量
typedef int Status;
typedef char ElemType;
typedef struct{ 
   
	ElemType *base;
	ElemType *top;
	int stacksize;
}sqStack; 
Status InitStack(sqStack &s){ 
   
	s.base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!s.base){ 
   
		exit(1);
	}
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return 0;
}
ElemType GetTop(sqStack s){ 
   //获取栈顶元素 
	ElemType e;
	if(s.top==s.base){ 
   
		return 0;
	}
	e=*(s.top-1);
	return e;
}
Status Push(sqStack &s,ElemType e){ 
   //插入元素e为新的栈顶元素 

	if(s.top-s.base>=s.stacksize){ 
   //如果栈满,扩充空间 
		s.base = (ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!s.base){ 
   
		exit(1);
		}
		s.top=s.base+s.stacksize; 
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;//赋值后栈顶指针+1 
	return 0;
}
Status Pop(sqStack &s,ElemType &e){ 
   //删除栈顶元素 
	if(s.top==s.base){ 
   
		return 1;
	}
	e = *--s.top;//栈顶指针-1,给e赋值 
	return 0;
}
Status In(ElemType c){ 
   
    if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')'||c=='['||c==']')
        return 1;
    else
        return 0;
}//In
char Precede(ElemType a, ElemType b){ 
   //判断运算符栈的 栈顶元素a和读入元素b的优先级 
    if(a=='+'||a=='-'){ 
   
        if(b=='+'||b=='-'||b=='>'||b=='#'||b==')'||b==']')
            return '>';
        else return '<';
    }
    if(a=='*'||a=='/'){ 
   
        if(b=='('||b=='[')
            return '<';
        else return '>';
    }
    if(a=='('){ 
   
        if(b==')')
            return '=';
        else return '<';
    }
    if(a=='['){ 
   
        if(b==']')
            return '=';
        else return '<';
    }
    if(a=='#'){ 
   
        if(b=='#')
            return '=';
        else return '<';
    }
}//Precede
ElemType Operate(ElemType a, ElemType x, ElemType b){ 
   //进行运算的函数 
     switch (x){ 
   
     case '+':
         return a+b;
     case '-':
         return a-b;
     case '*':
         return a*b;
     case '/':
         return a/b;
     }
}//Operator
ElemType EvaluateExpression(){ 
   
	sqStack OPTR,OPND;//OPTR:运算符栈 OPND:运算数栈 
	char c,x;
	InitStack(OPTR);
	Push(OPTR,'#'); 
	InitStack(OPND);
	c=getchar();
	
	while(c!='#'||GetTop(OPTR)!='#'){ 
   

		if(!In(c)){ 
   
			Push(OPND,c-'0'); //不是运算符,进入运算数栈。 
			c=getchar();
		}
		else
			switch(Precede(GetTop(OPTR),c)){ 
   
				case '<':Push(OPTR,c);c=getchar();break;//栈顶元素优先级低 
				case '=':Pop(OPTR,x);c=getchar();break;//栈顶元素优先级低 
				case '>':
				Pop(OPTR,x);
				ElemType a, b;
                Pop(OPND, b);
				Pop(OPND, a);
				Push(OPND, Operate(a, x, b));
				break;
			}
	}
	return GetTop(OPND);
}
int main(){ 
   
	printf("%d",EvaluateExpression());
	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/147817.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 基于springboot的websocket聊天室[通俗易懂]

    基于springboot的websocket聊天室[通俗易懂]一、概述1.Http2.WebSocket3.Socket4.WebSocket和Http5.WebSocket和Socket6.长连接,短连接7.http和websocket的

  • Django(31)模板中常用的过滤器[通俗易懂]

    Django(31)模板中常用的过滤器[通俗易懂]模版常用过滤器在模版中,有时候需要对一些数据进行处理以后才能使用。一般在Python中我们是通过函数的形式来完成的。而在模版中,则是通过过滤器来实现的。过滤器使用的是|来使用。add将传进来的参

  • mac 文字识别软件ocr_Mac平台上一款免费的OCR文字识别功能的屏幕截图软件Screen OCR…

    mac 文字识别软件ocr_Mac平台上一款免费的OCR文字识别功能的屏幕截图软件Screen OCR…今天小编为大家带来Mac平台上一款免费的OCR文字识别功能的屏幕截图软件ScreenOCRforMac(屏幕截图OCR工具)​www.macdown.com。使用这款截图ocr识别工具可以帮助用户从屏幕截图中获取不可复制文本。ScreenOCRMac版软件介绍ScreenOCRforMac是一款非常简单易用的Mac桌面图片转文字的工具。通过设置快捷键,捕捉屏幕图像,调用OCR功能,…

  • chrome小恐龙源代码_chrome小恐龙代码

    chrome小恐龙源代码_chrome小恐龙代码Chrome小恐龙前端修改代码代码总结偶然间发现谷歌浏览器的离线小恐龙游戏,上网查找的攻略总结。Chrome小恐龙是什么?在Chrome(谷歌浏览器)断网之后访问在线页面,如a.com会出现以下

  • android toast 自定义时间,Android 自定义 Toast 显示时间「建议收藏」

    android toast 自定义时间,Android 自定义 Toast 显示时间「建议收藏」Android自定义Toast显示时间实现代码:packagecom.wm.realname.util;importandroid.content.Context;importandroid.os.Handler;importandroid.view.View;importandroid.widget.Toast;/***Toast自定义显示时间*使用方法*1.先初始化类M…

  • pycharm向左缩进_pycharm取消缩进快捷键

    pycharm向左缩进_pycharm取消缩进快捷键在使用pycharm时,经常会需要多行代码同时缩进、左移,pycharm提供了快捷方式1、pycharm使多行代码同时缩进鼠标选中多行代码后,按下Tab键,一次向右缩进四个字符2、pycharm使多行代码同时左移鼠标选中多行代码后,同时按住shift+Tab键,一次向左移四个字符另外:在使用pycharm过程中光标变粗,此时变成了改写模式,只需要按下键盘的insert键即可…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号