[栈] 表达式求值 – C语言(多位数求值,2位数以上)

[栈] 表达式求值 – C语言(多位数求值,2位数以上)【理论】https://blog.csdn.net/summer_dew/article/details/82048387【代码说明】支持:2位以上的数字,四则运算和幂运算使用的栈,是自己实现,封装在2SqStack.h文件中的,可自己实现,也可以参照:https://blog.csdn.net/summer_dew/article/details/82051767【结果】测试:…

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

相关链接:

  1. 表达式求值汇总
  2. 多位数表达求值

表达式

前缀表达式 中缀表达式 后缀表达式
表达式a×b + (c-d/e)×f + ×ab ×-c/def a×b + c-d/e×f ab× cde/ -f×+
定义 OP S1 S2 S1 OP S2 S1 S2 OP
计算结果 和原表达式相同 失去了括号导致结果和原表达式不同 和原表达式相同
计算过程 扫描到S2->往前找S1->再往前找OP->计算 没有意义 扫描到OP->往前找S2->往前找S1->计算

表达式求值

【步骤】表达式–>后缀表达式–>求值

  1. 表达式转后缀表达式:表达式至后缀表达式

  2. 后缀表达式求值:

    后缀表达式求值

表达式转后缀表达式

步骤

Stack OPND; //存储后缀【表达式】的栈
Stack OPTR; //存储【符号】的栈
OPTR.push('#') //将一个#压在最下面,做标识,为了更好统一比较

扫描原表达式,得到c
	if c==数字:
		放入OPND
	if c==符号:
		c前面的一个符号top(OPTR的栈顶元素)
		//c与top进行优先级比较
		if c<top:
			OPTR.pop()
			OPTR.push(top) //将c放入符号栈
		else if c>top:
			OPTR.push(c)  //将c放到符号栈
		else if c==top:
			continue

运算符表

运算符 c2
c1
+ * / ( ) ^ #
+ < < < < > < < >
< < < < > < < >
* > > < < > < < >
/ > > < < > < < >
( > > > > > > > >
) < < < < = < < >
^ > > > > > < > >
# < < < < < < < =

【说明】先运算则优先级大

  • 【行c1】扫描到的运算符c1
  • 【列c2】在C1之前的运算符c2

【例子】

  • 【例1】1+2+3

    • 扫描到c1=+(第二个+),c1前面的符号也是+(即c2=+,第一个+)
    • 应该先运算1+2,即c2应该先运算(第一个+),所以c1<c2
  • 【例2】1+(1…

    • 扫描到c1=’(’,c1前面的一个符号是+,即c2=+
    • 应该先运算括号里的,即c1先运算,所以c1’>’c2
  • 【例3】(1+1…

    • 扫描到c1=+,c1前面的一个符号是(,即c2=(
    • 应该运算1+1,等同于c1运算,(后运算,所以c1’>’c2
  • 【例4】…1)+2

    • 扫描到c1=+,c1前面的一个符号是)
    • 括号里的先运算,即)先运算,所以c1’<‘c2

【总结】抓住一个原则:c1前面的c2,如果c2先运算,即c1<c2
例如:+(c1)前面是+(c2),后面的+先与运算,即+<+

例子

表达式转后缀表达式

【代码】支持2位以上的数字

【代码说明】支持:2位以上的数字,四则运算和幂运算
使用的栈,是自己实现,封装在2 SqStack.h文件中的,可自己实现,也可以参照:https://blog.csdn.net/summer_dew/article/details/82051767
【结果】
测试:10*(1*(2+6/3)-1)+3^(3-1)+1+1-2# 结果为
这里写图片描述
这里写图片描述
这里写图片描述

// 顺序栈
// 顺序栈
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SElemType int
#include"2 SqStack.h"

void visit(SElemType e) { 
   
	printf("%d ",e);
}
void visit_optr(SElemType e) { 
   
	printf("%c ",e);
}
void Show(SqStack *pOPTR, SqStack *pOPND,char c) { 
   
	//printf("| 步骤 | 操作数栈OPND | 操作符栈OPTR | 输入字符 |\n");
	static int first = 1;
	if (first==1) { 
   
		printf("当前扫描的字符\t数字栈\t符号栈\n");
		first++;
	}
	printf("%c\t",c);
	StackTraverse(*pOPND, &visit);printf(" \t");
	StackTraverse(*pOPTR, &visit_optr);
	printf("\n");
}
//将操作符转换成矩阵下标
int getIndex(char c) { 
    
	switch(c) { 
   
	case '+': return 0;
	case '-': return 1;
	case '*': return 2;
	case '/': return 3;
	case '(': return 4;
	case ')': return 5;
	case '^': return 6;
	case '#': return 7;
	}
	return -1;
}
// 两个操作数比较
// c1>c2 TRUE
// c1<c2 FALSE
int compare_op(char c1,char c2) { 
   
	char result;
	static char priorityMatrix[8][8] = 
	{ 
     // + - * / ( ) ^ #
		{ 
   '<','<','<','<','>','<','<','>'}, //+
		{ 
   '<','<','<','<','>','<','<','>'}, //-
		{ 
   '>','>','<','<','>','<','<','>'}, //*
		{ 
   '>','>','<','<','>','<','<','>'}, ///
		{ 
   '>','>','>','>','>','>','>','>'}, //(
		{ 
   '<','<','<','<','=','<','<','>'}, //)
		{ 
   '>','>','>','>','>','<','>','>'}, //^
		{ 
   '<','<','<','<','<','<','<','='}  //#
	};
	// 转换下标
	int c1_index = getIndex(c1);
	int c2_index = getIndex(c2);
	// 矩阵
	result =  priorityMatrix[c1_index][c2_index];
	switch (result) { 
   
	case '<' : return -1; // c1<c2
	case '>' : return 1; // c1>c2
	case '=' : return 0; // c1=c2错误情况
	}
	return 0;
}
int Operate(int S1,char OP,int S2) { 
   
	switch (OP) { 
   
	case '+':
		return S1+S2;
	case '-':
		return S1-S2;
	case '*':
		return S1*S2;
	case '/':
		return S1/S2;
	
	case '^':
		return (int)pow(S1,S2);
	}
	return 0;
}

//表达式求值:规定为整数,未检查异常
/* 测试数据:
10+11+12#
10*(1*(2+6/3)-1)+3^(3-1)+1+1-2#
 */
int main() { 
   
	SqStack OPTR; //存放符号(操作符)
	SqStack OPND; //存放数值(操作数)
	char c; //每次获得的字符
	int num,S1,S2,result,tmp,OP; //存放数字
	//初始化
	InitStack(&OPTR);
	Push(&OPTR, '#');
	InitStack(&OPND);

	printf("请输入表达式:\n");
	c=getchar();
	num=0;
	while ( !StackEmpty(OPTR) ) { 
   
		if (c>='0' && c<='9') { 
    //数字
			num = num*10 + c-'0'; //保存数字

			Show(&OPTR, &OPND, c); //UI
			printf("\t\t\t\t【操作】是数字%d\n",num); //UI
		} else { 
    //操作符
			if (num!=0) { 
    //之前有数字
				Push(&OPND, num); //入栈
				printf("\t\t\t\t【操作】至此,前面的扫描中得到一个数字%d,入栈\n",num); //UI
				Show(&OPTR, &OPND, c); //UI
				num =0; //归为0
			}
			GetTop(OPTR, &OP); //取出操作符栈顶元素
			//与上一个符号比较优先级
			tmp = compare_op((char)c, (char)OP);
			printf("\t\t\t\t【操作】优先级比较:%c与%c\n",c,OP);
			if ( tmp==1 ) { 
    //c>tmp
				Push(&OPTR, c); //压栈

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】将符号%c压栈\n",c); //UI
			} else if ( tmp==-1 ){ 
    //c<tmp
				Pop(&OPTR, &OP);
				Pop(&OPND, &S2); //先取出的是后面一位的数字 
				Pop(&OPND, &S1);
				result = Operate(S1, (char)OP, S2);
				Push(&OPND, result);

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】进行计算%d%c%d=%d,将结果压栈\n",S1,OP,S2,result);//UI
			
				continue; //不执行c=getchar(),当前的c还没有处理完
			} else if (tmp==0){ 
   
				// 1. c=) OP=(
				// 2. c=# OP=#
				Pop(&OPTR,&tmp); //将栈顶删除

				Show(&OPTR, &OPND, c); //UI
				printf("\t\t\t\t【操作】当前操作符和栈顶操作符相同,删除栈顶操作符\n");
			}
			
		}
		c = getchar();
	}
	GetTop(OPND,&result);
	printf("\n计算结果:%d\n", result);
	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现(Eureka)[通俗易懂]

    史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现(Eureka)[通俗易懂]springcloud为开发人员提供了快速构建分布式系统的一些工具,包括配置管理、服务发现、断路器、路由、微代理、事件总线、全局锁、决策竞选、分布式会话等等。它运行环境简单,可以在开发人员的电脑上跑。另外说明springcloud是基于springboot的。本文主要介绍了服务的注册与发现。

  • 算法java实现–动态规划–电路布线问题

    算法java实现–动态规划–电路布线问题

  • 教你画出业务架构图「建议收藏」

    教你画出业务架构图「建议收藏」1、什么是业务架构图?业务架构图是一种表达业务层级和关系的工具,业务架构服务于业务目标,通过描绘业务上下层关系,梳理一整套完整、简单的业务视图,降低业务系统的复杂度,提高客户理解度,最终给客户最直观的业务体现。2、业务架构图的三大核心要义简单来说可以分为三个核心步骤:分层、分模块、分功能。架构图核心要义之一:分层指的是将业务按照层级区分,每个层级都属于独立的版块。下层更抽象,上层更具体。层级需要有逻辑上的关联,比如下层为上层服务,或者提供能力支撑。架构图核心要义之二:分模块分

    2022年10月12日
  • 编程画爱心代码_程序员爱心代码

    编程画爱心代码_程序员爱心代码520情人节送到那个你所疼爱的人

    2022年10月13日
  • Mahout-Pearson correlation的实现

    Mahout-Pearson correlation的实现

  • mongodb菜鸟教程_mongodb怎么用

    mongodb菜鸟教程_mongodb怎么用MongoVUE是一个关于mongodb数据库管理的工具,并且免费,但超过15天后功能受限。我们可以通过删除mongodb相应的注册表项来解除限制。其步骤如下:1.运行‘win+R’;2.输入‘regedit’,如下图所示:3.进入注册表编辑器,找到与mongodb相关的注册表项,并将里面的注册表项全部删除,如下所示:4.最后可以发现mongovue可以正常使用了,mongovue被激活成功教程了。5.细…

发表回复

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

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