文档章节

表达式(四则运算)计算的算法

自由的角马
 自由的角马
发布于 2015/01/10 13:58
字数 1845
阅读 36
收藏 0

表达式(四则运算)计算的算法

戏剧前奏——基本知识点

通常我们所看到的算术表达式,运算符总是在两个操作数中间(),如(A+B)*C这样的表达式叫做中缀表达式。这种表达式不同的运算符优先级不同,而且通常含有括号,计算机很难理解这种表达式。在编译系统中,要把人易于理解的表达式翻译成能正确求值的机器指令。编译系统中对中缀形式的算术表达式的处理方式是先把中缀表达式转换成后缀表达式,再进行计算。

后缀表达式是表达式中的运算符出现在操作数的后面,并且不含括号,如AB+C*。后缀表达式的特点:

(1).后缀表达式让操作数和中缀表达式的操作数先后次序相同,只是运算符的先后次序改变;

(2).后缀表达式没有括号,运算次序就是其执行次序。

在计算机内部,任何一个表达式都是由操作数、运算符和分界符组成。操作数和运算符是表达式的主要部分,分界符(如用#表示)标志了一个表达式的结束。我们把操作数、运算符和分界符称为表达式的单词

一个中缀表达式的四则运算规则:

1.先乘除后加减

2.先括号内后括号外

3.同级别时先左后右

下面以A+(B-C/D)*E为例对过程进行讲解。A+(B-C/D)*E转换成后缀表达式后为

ABCD/-E*+

其运算次序为:T1=CD/; T2=BT1-; T3=T2E*; T4=AT3+

基于后缀表达式的两个特点,计算过程如下:计算时只要从左到右依次扫描后缀表达式的各个单词,当读到的单词为运算符时,就对该运算他会前两个操作数进施以此运算所代表的操作,然后将结果T插入到后缀表达式中再重复上面的操作。

享受过程——实现步骤和方法

根据以上的讲解,可初步地列出实现的步骤如下:

1.把中缀表达式的字符中提取出一系列表达式单词;

2.把中缀表达式单词系列转换成后缀表达式单词系列;

3.对后缀表达式词系列依次进行计算。

下面依次对各个步骤进行讲解。

把中缀表达式的字符中提取出一系列表达式单词

要提取表达式单词,首先要定义一个单词的类。该类要有两个属性:是否为操作数的标记;数据元素

代码:

package cn.eddu.jxau.calculation;

public class DataType {
	//是否为操作数
	private boolean isNum;
	//数据元素
	private Object data;
	public DataType() {
		isNum = false;
		data = null;
	}
	public DataType(boolean isNum, Object data) {
		this.isNum = isNum;
		this.data = data;
	}
	//get和set方法
	//......
}


将算式表达式转换成操作数和运算符,放入队列中

代码:

private static void splitExpress(String str, String... regexs) {
			StringBuilder strBuilder = new StringBuilder();
			for (int i = 0; i < regexs.length; i++) {
				if (i == regexs.length - 1) {
					strBuilder.append("[").append(regexs[i]).append("]");
				} else {
					strBuilder.append("[").append(regexs[i]).append("]|");
				}
			}
			Pattern p = Pattern.compile(strBuilder.toString());
			Matcher m = p.matcher(str);
			List<String> strList = new ArrayList();
			int strStart = 0; // 分割单词的首位置
			String s; // 分割的单词
			Double d;
			while (m.find()) {
				s = str.substring(strStart, m.start()).trim();
				if (!s.equals(new String())) {
					d = Double.parseDouble(s);
					pressQ.push(new DataType(true, d));
				}
				strStart = m.end();
				
				s = str.substring(m.start(), m.end());
				pressQ.push(new DataType(false, s));
			}
			s = str.substring(strStart, str.length()).trim();
			if (!s.equals(new String())) {
				d = Double.parseDouble(s);
				pressQ.push(new DataType(true, d));
			}
	}


把中缀表达式单词系列转换成后缀表达式单词系列

中缀表达式转换成后缀表达式的算法步骤:(1).设置一个堆栈S,初始时将栈顶元素设置为#(2).顺序读入中缀表达式,当读到的单词为操作数时将其加入到线性表L, 并接着读下一个单词。(3).x1为当前栈顶运算符的变量,x2为当前扫描读到的运算符的变量,当顺序从中缀表达式中读入的单词为运算符时就赋予x2;然后比较x1x2的优先级,若优先级x1>x2,将x1S中出栈,并加入L中,接着比较新的栈顶运算符x1x2的优先级;若优先级x1<x2,将x2入栈S,接着读下一个单词;若优先级x1=x2x1(x2),x1出栈,接着读下一个单词;若优先级x1=x2x1#x2#,算法结束。

各运算符优先级关系表

x2

x1

+

-

×

÷

(

)

#

+

>

>

<

<

<

>

>

-

>

>

<

<

<

>

>

×

>

>

>

>

<

>

>

÷

>

>

>

>

<

>

>

(

<

<

<

<

<

=

$

)

>

>

>

>

$

>

>

#

<

<

<

<

<

$

=

表中x1+-x2*/时,优先级x1<x2,满足中缀表达式规则1.先乘除后加减;x1为+-*/x2(/时,优先级x1<x2,满足中缀表达式规则2.先括号内后括号外;x1的运算符x2的运算符同级别时,优先级x1=x2,满足中缀表达式规则3.同级别时先左后右。出现表中的$表示中缀表达式语法出错。


中缀表达式转换成后缀的过程

步骤

中序表达式

堆栈

输出

1

A+(B-C/D)*E#

#

2

+(B-C/D)*E#

#

A

3

(B-C/D)*E#

#+

A

4

B-C/D)*E#

#+(

A

5

-C/D)*E#

#+(

AB

6

C/D)*E#

#+(-

AB

7

/D)*E#

#+(-

ABC

8

D)*E#

#+(-/

ABC

9

)*E#

#+(-/

ABCD

10

*E#

#+(-

ABCD/

11

*E#

#+(

ABCD-

12

*E#

#+

ABCD-

13

E#

#+*

ABCD-

14

#

#+*

ABCD-E

15

#

#+

ABCD-E*

16

#

#

ABCD-E*+


代码:

/**
	 * 将队列中的操作数和运算符转换成后缀表达式
	 * @return
	 */
	private static void toPostfix() {
		sigStack.push("#");
		pressQ.push(new DataType(false, "#"));
		String topSign = null;
		DataType datatype = null;
		String sign = null;
		while(!sigStack.isEmpty() && !pressQ.isEmpty()) {
			topSign = (String)sigStack.peek();
			datatype = (DataType)pressQ.peek();
			if(datatype.isNum()) {	//取出的是操作数
				suffixL.add(datatype);
				pressQ.pop();
			} else {				//取出的是运算符
				sign = (String)datatype.getData();
				if(sign.matches("[\\+\\-\\*[/()#$]]{1}")) {
					if(">".equals(signMap.getValue(topSign, sign))) {
						suffixL.add(new DataType(false, sigStack.pop()));
					} else if("<".equals(signMap.getValue(topSign, sign))) {
						sigStack.push(sign);
						pressQ.pop();
					} /*else if("=".equals(signMap.getValue(topSign, sign)) && topSign.equals("(") && sign.equals(")")) {
						sigStack.pop();
						pressQ.pop();
					} */else if("=".equals(signMap.getValue(topSign, sign))&& topSign.equals("#")) {
						break;
					} else if(sign.equals(")")) {
						if("=".equals(signMap.getValue(topSign, sign)) && topSign.equals("(")) {
							sigStack.pop();
							pressQ.pop();
						} else {
							while(">".equals(signMap.getValue(topSign, sign))) {
								suffixL.add(new DataType(false, sigStack.pop()));
								topSign = (String)sigStack.peek();
							}
						}
					} else {
						try {
							throw new Exception("算术表达式错误!");
						} catch (Exception e) {
							e.printStackTrace();
						}
					}
				}
			}
		}
	}


对后缀表达式词系列依次进行计算。

计算时只要从左到右依次扫描后缀表达式的各个单词,当读到的单词为运算符时,就对该运算他会前两个操作数进施以此运算所代表的操作,然后将结果T插入到后缀表达式中再重复上面的操作。

代码:

DataType e = null;
		double d1, d2, d;
		d1 = d2 = d =0;
		int i = 0;
		while(!suffixL.isEmpty() && i < suffixL.size()) {
			e = suffixL.get(i);
			if(!e.isNum()) {
				String sign = (String)e.getData();
				d1 = (Double)suffixL.get(i-2).getData();
				d2 = (Double)suffixL.get(i-1).getData();
				if("+".equals(sign)) {
					d = d1+d2;
				} else if("-".equals(sign)) {
					d = d1-d2;
				} else if("*".equals(sign)) {
					d = d1*d2;
				} else if("/".equals(sign)) {
					d = d1/d2;
				} else {
					try {
						throw new Exception("表达式出错!");
					} catch (Exception e1) {
						// TODO Auto-generated catch block
						e1.printStackTrace();
					}
				}
				suffixL.remove(i-2);
				suffixL.remove(i-2);
				suffixL.set(i-2, new DataType(true, d));
				i = i-2;
			}
			i++;

见证奇迹——实例测试

测试代码:
package cn.eddu.jxau.calculation;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(Calculation.calculate("(4-4/7)*7"));//"12+(40-6/3)*4"   (6+4)*5
		System.out.println((4-4/7)*7);
	}
	
}

结果:

24.0
28


可以发现通过转换成后缀表达式后的计算比较直接的写计算式不要准确,直接表达式会将一步计算的结果转化成int类型的数后再进行计算。

追根究底——源码下载


本文转载自:http://blog.csdn.net/luoweifu/article/details/10477447

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
Qt之加减乘除四则运算-支持负数

一、效果展示 如图1所示,是简单的四则运算测试效果,第一列为原始表达式,第二列为转换后的后缀表达式,冒号后为结果。表达式支持负数和空格,图中是使用了5组测试数据,测试结果可能不全,...

朝十晚八
2018/07/23
0
0
逆波兰式的学习、运用(附带C++写的一个整数的计算器)

我们今天普遍使用计算器,在初级的计算器中,由于计算机可没有人那么聪明,很难能够准确得判断运算的优先级,所以在写计算机的计算器的时候,我们需要将获得的四则运算的表达式改写为逆波兰式...

猜猜我是吧
2014/05/30
1K
1
求24点,算术式解析

题目: 给定任意4个正整数,利⽤用加,减,乘,除,括号这⼏几个运算符,编程计 算所有由这4个数字计算出24的表达式,并输出计算表达式。 输出结果要求:加法,乘法需要去重,(( a + b ) c)...

梦想游戏人
2016/10/26
55
0
数据结构与算法之Stack(栈)的应用——用stack实现一个计算器——in dart

本文用stack实现了一个计算器,支持括号、小数、负数。代码比较简单,没加什么注释。实际使用时,读取用户在stdin的输入,然后计算。若格式错误,会抛出异常。 在实际计算过程中,实际分为三...

Burkut
01/15
0
0
PHP实现逆波兰式 - 计算工资时用

近期一个小项目需要用到公式运算, 所以就进行一些了解,以下内容均属于个人经验。 在PHP中实现公式表达式四则运算大概有两种方法: 1)使用系统函数eval 2)将表达式转换成逆波兰表达式进行计...

邪恶的小Y
2011/10/08
268
1

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部