当前位置：网站首页 > 技术资源 > 正文

使用栈实现中缀表达式计算器（用栈实现中缀表达式到后缀表达式的转换）

off999 2024-10-02 18:36 47 浏览 0 评论

计算器实现原理分析

0. 准备工作：

(1) 一个用来存储数值的数值栈：numStack

(2) 一个用来存储运算符的运算符栈：operStack

1. 将字符串表达式拆分，然后逐个扫描。

(1) 如果是数字，直接压入数值栈

(2) 如果是运算符

1 如果当前运算符栈为空，直接将运算符压入运算符栈

2 如果运算符不为空

1) 如果当前运算符的优先级高于运算符栈栈顶的运算符，则直接压入运算符栈

2) 如果当前运算符的优先级小于或等于运算符栈栈顶的运算符，则需要将栈顶的运算符弹出，同时需要从数值栈中弹出两个数，与栈顶运算与进行运算，然后将运算结果重新压入数值栈。最后继续判断当前运算符与栈顶运算符的优先级，重复该步骤。

2. 表达式扫描完成后，如果运算符栈不为空，则弹出栈顶运算符，同时弹出数值栈中的两个数，进行运算，将结果重新压入数值栈，直到运算符栈为空，此时数值栈中的最后一个数值即为表达式的运算结果。

表达式入栈原理图解

表达式为：2*3*2+4-5-6*2，首先将表达式拆分为

"2"，"*"，"3"，"*"，"2"，"+"，"4"，"-"，"5"，"-"，"6"，"*"，"2"

1. 扫描第一个字符串，判断为数字 "2"，直接压入数值栈

2. 扫描第二个字符串，判断为运算符"*"，运算符栈为空，直接压入运算符栈

3. 扫描第三个字符串，判断为数字"3"，直接压入数值栈

4. 扫描第四个字符串，判断为运算符"*"，运算符栈不为空，与栈顶的运算符 * 优先级相等，需要进行运算

1）首先弹出运算符栈栈顶的 *

2）弹出数值栈中的 3

3）弹出数值栈中的 2

4）将 3 * 2 的结果重新压入数值栈

5）将第四个字符串的*压入运算符栈

5. 扫描第五个字符串，判断为数值"2"，直接压入数值栈

6. 扫描第六个字符串，判断为运算符 "+"，继续与运算符栈顶进行优先级比较。结果为小于

1）首先弹出运算符栈栈顶的 *

2）弹出数值栈中的 2

3）弹出数值栈中的 6

4）将 2 * 6 的结果重新压入数值栈

5）将第六个字符串的+压入运算符栈

7. 扫描第七个字符串，判断为数值"4"，直接入数值栈

8. 扫描第八个字符串，判断为运算符 "-"，继续与运算符栈顶进行优先级比较。结果为等于

9. 扫描第九个字符串，判断为数值"5"，直接入数值栈

10. 扫描第十个字符串，判断为运算符 "-"，继续与运算符栈顶进行优先级比较。结果为等于

1）首先弹出运算符栈栈顶的 -

2）弹出数值栈中的 5

3）弹出数值栈中的 16

4）将 16 - 5 的结果重新压入数值栈

5）将第十个字符串的-压入运算符栈

11. 扫描第十一个字符串，判断为数值"6"，直接入数值栈

12. 扫描第十二个字符串，判断为运算符 "*"，继续与运算符栈顶进行优先级比较。结果为大于

13. 扫描第十三个字符串，判断为数值"2"，直接入数值栈

表达式解析入栈过程

计算过程图解

表达式为：2*3*2+4-5-6*2，解析完成后，栈内情况如下图所示

重复如下步骤，直到运算符栈为空：

1）从 operStack 栈弹出一个运算符

2）从 numStack 栈弹出两个数据

3）计算结果后将结果重新压入数值栈

中缀表达式计算器代码实现

/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: MyCalculator.java 
 * @Package com.tuling.calculator 
 * @Description: 
 * @author: 小白 
 * @Date 2019年12月3日 下午3:28:03 
 * @version V1.0 
 * @Copyright: 
 */ 
package com.tuling.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @ClassName MyCalculator
 * @Description 中缀表达式实现计算器
 * @Author 北京图灵学院
 * @Date 2019年12月3日 下午3:28:03
 */
public class MyCalculator {
	
	//数值栈
	private MyStack numStack;
	//运算符栈
	private MyStack operStack;
	
	//ArrayList 用来存放表达式拆分后的字符串
	private List<String> sourceExp;

	/** 
	 * @Title: MyCalculator 
	 * @Description: 
	 * @param: 
	 * @throws 
	 */ 
	public MyCalculator() {
		numStack = new MyStack(10);
		operStack = new MyStack(10);
		sourceExp = new ArrayList<String>();
	}
	
	/**
	 * 
	 * @Title: calculate 
	 * @Description:计算 
	 * @param: @param expression
	 * @param: @return 
	 * @return: int 
	 * @throws
	 */
	public int calculate(String expression) {
		//先将原始表达式拆分
		getExp(expression);
		
		//将原始表达式逐个解析，入栈
		inStack(sourceExp);
		
		//入栈完成，依次从运算符栈弹出一个运算符，从数值栈弹出两个数，进行运算。
		while(!operStack.isEmpty()) {
			//弹出当前运算符栈顶的运算符
			String oper = operStack.pop();
			String num1 = numStack.pop();
			String num2 = numStack.pop();
			
			//计算结果
			int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);
			
			//将结果压入数值栈
			numStack.push(result+"");
		}
		//将数值栈的数返回。
		return Integer.parseInt(numStack.pop());
	}

	/**
	 * @param list 
	 * @Title: inStack 
	 * @Description:将原始表达式逐个解析，进行入栈操作 
	 * 	遍历集合，拿到每一个元素并且判断 
 	 * 		1.如果是运算符
	 * 			1.1> 如果当前运算符栈不为空：
	 * 				1.1.1> 如果当前运算符的优先级小于或者等于栈顶的运算符优先级
	 * 						从数值栈中弹出两个数，并且将运算的结果压入数值栈
	 * 						将运算符压入运算符栈
	 * 				1.1.2> 否则：直接压入运算符栈
	 * 			1.2> 如果当前运算符栈为空：直接压入运算符栈
	 * 		2.如果是数值：
	 * 			直接压入数值栈
	 * @param: 
	 * @return: void 
	 * @throws 
	 */
	private void inStack(List<String> list) {
		for(String str:list) {
			if(isOper(str)) {
				//判断
				if(operStack.isEmpty()) {
					//运算符栈为空，直接入栈
					operStack.push(str);
				}else {
					//不为空，需要与栈顶运算符比较优先级高低
					//如果当前运算符的优先级小于或等于运算符栈顶的优先级，需要运算
					if(priority(str) <= priority(operStack.peek())) {
						//需要运算，
						//弹出当前运算符栈顶的运算符
						String oper = operStack.pop();
						String num1 = numStack.pop();
						String num2 = numStack.pop();
						
						//计算结果
						int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);
						
						//将结果压入数值栈
						numStack.push(result+"");
						
						//将运算符压入运算符栈
						operStack.push(str);
						
					}else if(priority(str) > priority(operStack.peek())) {
						//直接入运算符栈
						operStack.push(str);
					}
				}
			}else if(isNum(str)) {
				//数字，直接入数值栈
				numStack.push(str);
			}
		}
	}
	
	public int cal(int num1,int num2,String oper) {
		int result = 0;
		switch (oper) {
			case "+":
				result = num1 + num2;
				break;
			case "-":
				result = num2 - num1;
				break;
			case "*":
				result = num1 * num2;
				break;
			case "/":
				result = num2 / num1;
				break;
			default:
				break;
		}
		return result;
	}
	
	/**
	 * 
	 * @Title: priority 
	 * @Description:返回运算符的优先级 
	 * @param: @param oper
	 * @param: @return 
	 * @return: int 
	 * @throws
	 */
	public int priority(String oper) {
		switch (oper) {
			case "*":
			case "/":
				return 2;
			case "+":
			case "-":
				return 1;
		default:
			return 0;
		}
	}

	/** 
	 * @Title: isNum 
	 * @Description:判断是否为数字 
	 * @param: @param str
	 * @param: @return 
	 * @return: boolean 
	 * @throws 
	 */
	private boolean isNum(String str) {
		return str.matches("[0-9]+");
	}

	/** 
	 * @Title: isOper 
	 * @Description:判断是否为运算符 
	 * @param: @param str
	 * @param: @return 
	 * @return: boolean 
	 * @throws 
	 */
	private boolean isOper(String str) {
		return str.matches("[\\+\\-\\*\\/]");
	}

	/** 
	 * @Title: getExp 
	 * @Description:将原始表达式拆分为字符串 
	 * @param: @param expression 
	 * @return: void 
	 * @throws 
	 */
	private void getExp(String expression) {
		StringTokenizer stringTokenizer = new StringTokenizer(expression, "+-*/", true);
		while(stringTokenizer.hasMoreTokens()) {
			sourceExp.add(stringTokenizer.nextToken());
		}
	}
}

测试类代码如下：

/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: Test.java 
 * @Package com.tuling.calculator 
 * @Description: 
 * @author: 小白 
 * @Date 2019年12月3日 下午7:28:33 
 * @version V1.0 
 * @Copyright: 
 */ 
package com.tuling.calculator;

/**
 * @ClassName Test
 * @Description 
 * @Author 北京图灵学院
 * @Date 2019年12月3日 下午7:28:33
 */
public class Test {

	/** 
	 * @Title: main 
	 * @Description: 
	 * @param: @param args 
	 * @return: void 
	 * @throws 
	 */
	public static void main(String[] args) {
//		String expression = "2+3*4";
		String expression = "2*3*4+5-6-4*2";
		
		MyCalculator mc = new MyCalculator();
		int result = mc.calculate(expression);
		System.out.println("表达式：" + expression + " = " + result);
	}

}

python 计算器