首页 > 其他分享 >表达式求值

表达式求值

时间：2023-06-15 21:56:21浏览次数：38  
标签：return 入栈 栈顶 next 运算符 操作符 求值 表达式

栈的应用—表达式求值

表达式通常由三部分组成：①操作数②运算符③界限符(括号等)

常见表达式有以下几种：

  1. 中缀表达式：\(a+b\)、\(a\backslash b\)、\(a+b-c\)、\(a+b-c*d\)

    特点：运算符在两个数中间

  2. 后缀表达式(逆波兰表达式)：\(ab+\)、\(ab\backslash\)、\(ab+c-\)、\(ab+cd*-\)

    特点：运算符在两个操作数后面

  3. 前缀表达式(波兰表达式)：\(+ab\)、\(\backslash ab\)、\(-+abc\)、\(-+ab*cd\)

    特点：运算符在操作数前面

1. 中缀表达式转后缀方法

遵循左优先原则。

①确定运算顺序

②选择下一个运算符，按照\([左操作数\) \(右操作数\) \(运算符]\)的方式组合成一个新的操作数

③如果还有运算符没被处理，继续②

如\(中缀表达式((15÷(7-(1+1)))\times3)-(2+(1+1))\)转换为后缀步骤：

  1. \(1\) \(1\) \(+\)
  2. \(7\) \(1\) \(1\) \(+\) \(-\)
  3. \(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\)
  4. \(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\) \(3\) \(\times\)
  5. \(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\) \(3\) \(\times\) \(1\) \(1\) \(+\)
  6. \(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\) \(3\) \(\times\) \(2\) \(1\) \(1\) \(+\) \(+\)
  7. \(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\) \(3\) \(\times\) \(2\) \(1\) \(1\) \(+\) \(+\) \(-\)

2 后缀表达式计算

通过上面我们将中缀表达式转为后缀表达式\(15\) \(7\) \(1\) \(1\) \(+\) \(-\) \(÷\) \(3\) \(\times\) \(2\) \(1\) \(1\) \(+\) \(+\) \(-\)

计算后缀表达式也不难：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算
合体为一个操作数。注意：两个操作数的左右顺序。

步骤：

  1. 第一个运算符是\(+\)，先算\(1+1\)
  2. 第二个运算符是\(-\)，\(7-2\)
  3. 第三个运算符是\(÷\)，\(15÷5\)
  4. 第四个运算符是\(\times\)，\(3\times3=9\)
  5. 第五个运算符是\(+\)，\(1+1\)
  6. 第六个运算符是\(+\)，\(2+2=4\)
  7. 最后一个运算符是\(-\)，\(9-4\)得最后结果

后缀表达式计算图示：

后缀表达式计算

3 代码实现

代码实现需要遵循以下几点：

①遇到操作数直接入栈

②遇到界限符'\((\)'，直接入栈，遇到'\()\)'，依次弹出栈内的运算符，直到栈顶元素为'\((\)'。

③运算符运算弹出规则，应该是：操作符栈顶运算符大于或等于当前输入运算符则弹出栈顶操作符。数字栈依次弹出两个数字\(num1,num2\)，运算是\(num2+-...num1\)

\(\Large 例:计算中缀表达式((15÷(7-(1+1)))\times3)-(2+(1+1))\)

Ⅰ.先分析运算符生效顺序，如下图:

运算符生效顺序

Ⅱ. 从左到右依次扫描入栈:操作符栈(charStack),操作数栈(numStack)

Ⅲ. 定义操作符优先级：\(+/-\)为\(A\)，\(\times/÷\)为\(B\)，\((\)为\(C\).

Ⅳ. 进行扫描运算：

①输入'\((\)'，由于操作符栈为\(NULL\)，直接入栈。

②输入'\((\)'，操作符栈不为\(NULL\)，且优先级等于操作栈顶的元素'('，但由于括号不参与运算，所以直接入栈。

③输入\(15\)，数字直接入栈。

④输入'\(÷\)'，由于'÷'优先级低于操作符栈顶元素'('，直接入栈。

⑤输入'\((\)'，括号直接入栈。

⑥输入\(7\)，数字直接入栈。

⑦输入'\(-\)'，'\(-\)'y优先级低于操作符栈顶元素'\((\)'，入栈。

⑧输入'\((\)'，直接入栈

⑨输入\(1\)，入栈

⑩输入'\(+\)'，'\(+\)'优先级低于操作符栈顶元素'\((\)'，入栈

⑪输入\(1\)，入栈。此时栈中元素情况如下：

操作符栈和操作数栈：

运算栈

⑫输入'\()\)'，栈顶操作符一次出栈直到为NULL或者为'\((\)'。此时弹出操作符栈顶元素'\(+\)'，弹出操作数栈前两个元素\(1,1\)。之后运算\(1+1\)得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈2

⑬输入')'，再次重复上面，弹出操作符栈顶元素'\(-\)'，弹出操作数栈两个元素\(2,7\)，运算\(7-2\)。得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈3

⑭输入'\()\)'，重复上面过程，弹出操作符栈顶元素'\(÷\)'，弹出操作数栈两个元素\(5,15\)，运算\(15÷5\)。得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈4

⑮输入'\(\times\)'，此时操作符栈顶元素为'\((\)'，优先级低于栈顶元素，直接入栈。

⑯输入'\(3\)'，直接入栈

运算栈5

⑰输入'\()\)'，弹出操作符栈顶元素'\(\times\)'，弹出操作数栈两个元素\(3,3\)，运算\(3\times3\)。得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈6

⑱输入'\(-\)'，此时操作栈为NULL，直接入栈

⑲输入'\((\)'，入栈

⑳输入\(2\)，入栈

㉑输入'\(+\)'，优先级小于操作栈顶元素'\((\)'，入栈

㉒输入'\((\)'，直接入栈

㉓输入\(1\)，入栈

㉔输入'\(+\)'，优先级低于操作栈栈顶元素'\((\)'，入栈

㉕输入\(1\)，入栈

运算栈7

㉖输入'\()\)'，弹出操作符栈顶元素'\(+\)'，弹出操作数栈两个元素\(1,1\)，运算\(1+1\)。得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈8

㉗输入'\()\)'，弹出操作符栈顶元素'\(+\)'，弹出操作数栈两个元素\(2,2\)，运算\(2+2\)。得到新的数字重新放回操作栈顶部，再次执行弹出元素为'\((\)'，这次运算结束。

运算栈9

㉘弹出操作栈顶元素'\(-\)'，弹出操作数栈两个元素进行最后运算，得到结果为\(5\)

详细代码

#include <bits/stdc++.h>
#include<string>
#define MaxSize 20
using namespace std;

char arrGrad(char s){
	switch(s){
		case '+':
			return 'A';
		case '-':
			return 'A';
		case '*':
			return 'B';
		case '/':
			return 'B';
		default :
			return 'C'; 
	}
}

//存放运算符 
typedef struct linkC{
    char data;
	char grad;				
    struct linkC *next;		
} *linkChar;

//存放运算数 
typedef struct linkN{
    int data;				
    struct linkN *next;		
} *linkNum;	 

bool initCharNum(linkChar &c,linkNum &n,char (&s)[MaxSize]){
	memset(s,'\0',sizeof(s));
	c=(linkChar)malloc(sizeof(linkChar));
	n=(linkNum)malloc(sizeof(linkNum));
	if(c==NULL||n==NULL) return false;
	c->next=NULL;
	n->next=NULL;
	return true;
}

//操作符入栈 
bool pushChar(linkChar &c,char s){
	linkChar p;
	p=(linkChar)malloc(sizeof(linkChar));
	if(p==NULL) return false;
	if(s=='+'|s=='-'){
		p->data=s;
		p->grad=arrGrad(s);
		p->next=c->next;
		c->next=p;
		return true;
	}else if(s=='*'|s=='/'){
		p->data=s;
		p->grad=arrGrad(s);
		p->next=c->next;
		c->next=p;
		return true;
	}else if(s=='('){
		p->data=s;
		p->grad=arrGrad(s);
		p->next=c->next;
		c->next=p;
		return true;
	}else{
		return false;
	}	
}

//操作数入栈 
bool pushNum(linkNum &n,int e){
	linkNum p;
	p=(linkNum)malloc(sizeof(linkNum));
	if(p==NULL) return false;
	p->data=e;
	p->next=n->next;
	n->next=p;
	
	return true;
}

//操作符出栈
char popChar(linkChar &c){
	char s;
	linkChar p;
	if(c->next==NULL) return 'E';
	s=c->next->data;
	p=c->next;
	c->next=p->next;
	free(p);
	return s;
}

//操作数出栈
int popNum(linkNum &n){
	int i;
	linkNum p;
	if(n->next==NULL) return 0;
	i=n->next->data;
	p=n->next;
	n->next=p->next;
	free(p);
	return i;
}

//获取操作符栈顶元素
char selectChar(linkChar &c,int e){
	if(e) return c->next->data;
	return c->next->grad;
}

//运算
void ope(linkChar &c,linkNum &n){
	char popchar=popChar(c);
	int num1=popNum(n);
	int num2=popNum(n);
	cout<<num2<<popchar<<num1<<endl;
	switch(popchar){
		case '+':
			pushNum(n,num2+num1);
			break;
		case '-':
			pushNum(n,num2-num1);
			break;
		case '*':
			pushNum(n,num2*num1);
			break;
		case '/':
			pushNum(n,num2/num1);
			break;
	}
} 

void printStack(linkChar &c,linkNum &n){
	while(c->next!=NULL){
		cout<<"data:"<<c->next->data<<"grad::"<<c->next->grad<<endl;
		c=c->next;
	}
	while(n->next!=NULL){
		cout<<"result:"<<n->next->data<<endl;
		n=n->next;
	}
}

//字符转数字 
int opeNum(char (&s)[MaxSize]){
	int couts,sum=0;
	for(int i=0;i<strlen(s);i++){
		couts=s[i]-'0';
		for(int j=i;j<strlen(s)-1;j++){
			couts=couts*10;
		}
		sum+=couts;
	}
	memset(s,'\0',sizeof(s));
	return sum;
}
int con=0;

//区分操作数和操作符
bool isCharNum(linkChar &c,linkNum &n,char s,char (&chrs)[MaxSize]){
	int i;
	if(s>='0'&&s<='9'){													//数字直接存入操作数栈 
		chrs[con++]=s;
		return true;
	}else if(s=='+'||s=='-'||s=='*'||s=='/'||s=='('||s=='!'){			//判断是否是操作符 
		if(strlen(chrs)>0) {
			i=opeNum(chrs);
			pushNum(n,i);
			con=0;
		}
		if(c->next==NULL){												//操作符栈为空，直接入栈 
			pushChar(c,s);
			return true;
		}
		if(selectChar(c,0)>=arrGrad(s)&&selectChar(c,1)!='('){			//不为空且栈顶操作符优先级大于等于当前所输入操作符元素,并且不是"("
			while(c->next!=NULL&&c->next->grad>=arrGrad(s)&&c->next->data!='('){			//取出操作符进行运算操作 
				ope(c,n);
			} 
		} 
		pushChar(c,s);													//将当前输入操作符压入栈顶 
		return true;
	}else if(s==')'){	
		if(strlen(chrs)>0||s=='!') {
			i=opeNum(chrs);
			pushNum(n,i);
			con=0;
		}															//如果当前输入是")",弹出所有操作符进行运算,直到碰到"(" 
		while(selectChar(c,1)!='('){
			ope(c,n);
		}
		popChar(c);														//弹出栈顶的"(" 
		return true;
	}else{
		return false;
	}
} 

int main(){
	char chr,chrs[MaxSize];
	linkChar c;
	linkNum n;
	initCharNum(c,n,chrs);
	while(chr!='!'){
		cin>>chr;
		isCharNum(c,n,chr,chrs);
	}
	ope(c,n);
	printStack(c,n);
}

更多知识内容点这里

标签：return,入栈,栈顶,next,运算符,操作符,求值,表达式
From： https://www.cnblogs.com/Acidm/p/17484211.html

相关文章

  • Javascript：正则表达式初学者指南（Regex） [a-zA-Z0-9]{4} 表示 包含大小写字母或者数字
    Javascript：正则表达式初学者指南（Regex）[a-zA-Z0-9]{4}表示包含大小写字母或者数字的字符串长度是4https://www.w3cschool.cn/article/55107251.html正则表达式是形成可以在字符串中搜索的模式的一组字符。正则表达式可用于验证，例如验证信用卡号，用于搜索，即通过复杂的文本匹配，......
  • 编程不懂正则表达式，不如回家种红薯
    编程不懂正则表达式，将有被淘汰的危险编程的大量工作都是在处理字符串，如验证输入、查找子串替换、解析HTML等，而正则表达式是一个极为强大的工具，它使我们需要很多行重复啰嗦的代码才能完成的编程任务，一个表达式就可以搞定，既节省时间又节省精力。但是学习它并不是一件轻松的事情，......
  • Spring之SpEL表达式操作示例解析
    目录1SpEL1.1简介1.2简单示例2深入示例2.1运算2.1.1算术运算2.1.2逻辑运算2.1.3比较运算2.1.4使用字符代替符号2.1.5使用正则表达式2.1.6使用instanceof2.1.7三目运算（if..else..）2.1.8表达式模板TemplateParserContext2.2字符串2.2.1操作2.2.2调用字符串方法2.3使......
  • Civil 3D 删除不需要的标签表达式
    正常情况下，不需要的标签表达式应该能够手动删除，不知道什么原因有些表达式在创建后状态就成了“被引用”状态，导致无法删除。即使想修改名称也不行，不得不采用编程的方式进行删除。代码如下：publicvoidm_RemoveExpression(){Documentdoc=......
  • VUE使用Element-ui表达式拼接字符串 el-table-column的prop拼接字符串 拼接table 使
    VUE使用Element-ui表达式拼接字符串el-table-column的prop拼接字符串使用<templateslot-scope="scope">更改td里面值https://blog.csdn.net/WindNolose/article/details/125422409描述VUE中的标签属性，可以在属性前使用：，让属性绑定到data中的动态数据el-table-column标......
  • Java正则表达式详解
    如果你曾经用过Perl或任何其他内建正则表达式支持的语言，你一定知道用正则表达式处理文本和匹配模式是多么简单。如果你不熟悉这个术语，那么“正则表达式”（RegularExpression）就是一个字符构成的串，它定义了一个用来搜索匹配字符串的模式。许多语言，包括Perl、PHP、Python、JavaScript......
  • c#用表达式树实现深拷贝功能
    因为对表达式树有点兴趣，出于练手的目的，试着写了一个深拷贝的工具库。支持.netstandard2.0或.netframework4.5及以上。GitHub地址https://github.com/blurhkh/DeepCopiernuget地址https://www.nuget.org/packages/DeepCopier使用方法如下：首先创建几个测试用的类型pub......
  • 正则表达式/\\\\/四个反斜杠
    本文摘自:https://blog.csdn.net/zttaiwx/article/details/53981755,放在自己博客后续方便查看在字符串中，两个反斜杠被解释为一个反斜杠，然后在作为正则表达式，\则被正则表达式引擎解释为\，所以在正则表达式中需要使用四个反斜杠。也就是说，前两个反斜杠在字符串中被解释为一个......
  • 正则表达式判断数字----来源百度
    正则表达式判断数字----来源百度https://blog.csdn.net/changbozizf/article/details/112960409数字：^[0-9]*$n位的数字：^\d{n}$至少n位的数字：^\d{n,}$m-n位的数字：^\d{m,n}$零和非零开头的数字：^(0|[1-9][0-9]*)$非零开头的最多带两位小数的数字：^([1-9][0-9]*)+(.[0-9]{1,2})?$带1......
  • 编译原理动手实操,用java实现编译器-算术表达式及其语法解析器的实现
     本节代码下载地址：http://pan.baidu.com/s/1sjWiwPn代码的理解和运行是吃透编译原理的关键，如果我们看的是爱情动作片，自然选择无码的好，但如果看得是计算机课程，则必须有码，无码的计算机理论都是耍流氓。当前，java所实现的简易编译器目的是将一条或一组含有加号和乘号的算术表达式编译......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99