package stack; import java.util.Stack; /** * Created by Lanxiaowei * Craated on 2016/12/11 17:29 * 使用栈计算表达式值 */ public class EvaluateExpression { public static void main(String[] args) { String exp = "(1+2+3)*10-2*2-6*2"; int result = calculate(exp); System.out.println("result:" + result); } /** * 从指定位置开始获取表达式中的操作数 * @param exp 表达式 * @param pos 起始索引位置 * @return */ public static String getDigt(String exp,int pos) { if(!Character.isDigit(exp.charAt(pos))) { //如果获取到的是左括号,返回提取操作数失败 if(exp.charAt(pos) == '(') { return "false"; } throw new IllegalArgumentException("Invalid expression:" + exp); } int num = 0; while(pos < exp.length() && Character.isDigit(exp.charAt(pos))) { num = num * 10 + exp.charAt(pos++) - '0'; } return num + ""; } /** * 获取指定位置的操作符 * @param exp * @param pos * @return */ public static char getOper(String exp,int pos) { switch (exp.charAt(pos)) { case '+' : case '-' : case '*' : case '/' : case '(' : case ')' : return exp.charAt(pos); default: throw new IllegalArgumentException("Invalid expression:" + exp); } } /** * 获取运算符的优先级 * @param oper * @return */ public static OperatorLevel getOperatorLevel(char oper) { switch (oper) { case '+' : case '-' : return OperatorLevel.LOW; case '*' : case '/' : return OperatorLevel.HIGH; default: throw new IllegalArgumentException("Invalid Operator:" + oper); } } /** * 计算两个操作数的值 * @param leftNum * @param oper * @param rightNum * @return */ public static int opt(int leftNum,char oper,int rightNum) { int result = 0; switch (oper) { case '+' : result = leftNum + rightNum; break; case '-' : result = leftNum - rightNum; break; case '*' : result = leftNum * rightNum; break; case '/' : //除数为零的情况 if (rightNum == 0) { throw new IllegalArgumentException("The divisor MUST NOT be zero"); } else { result = leftNum / rightNum; } break; default: throw new IllegalArgumentException("Invalid Operator:" + oper); } return result; } /** * 比较两个操作符的优先级 * @param oper1 操作符1 * @param oper2 操作符2 * @return */ public static boolean isGreater(char oper1,char oper2) { return getOperatorLevel(oper1).getValue() > getOperatorLevel(oper2).getValue(); } /** * 计算表达式求值 * @param exp * @return */ public static int calculate(String exp) { if(null == exp || "".equals(exp)) { throw new IllegalArgumentException("Invalid expression:" + exp); } exp = exp.replace(" ", ""); exp = "(" + exp + ")"; //操作数栈 Stack<Integer> numStack = new Stack<Integer>(); //操作符栈 Stack<Character> operStack = new Stack<Character>(); int status = 0; int pos = 0; Integer tempNum = 0; char tempOper = '0'; char tempOper2 = '0'; int leftNum = 0; int rightNum = 0; String tem = ""; while (pos < exp.length()) { switch (status) { case 0: //提取操作数 //如果提取操作数不成功,则进入status=2步骤 tem = getDigt(exp, pos); if ("false".equals(tem)) { status = 2; break; } tempNum = Integer.valueOf(tem); //操作数压栈 numStack.push(tempNum); //进入步骤1 status = 1; pos = pos + tem.length(); break; case 1: //提取操作符 tempOper = getOper(exp,pos); //如果提取到的是左括号,则抛出异常 if(tempOper == '(') { throw new IllegalArgumentException("Invalid expression:" + exp); } //如果提取到的是右括号,则需要进行计算 if(tempOper == ')') { while (true) { //获取栈顶元素 tempOper = operStack.peek(); operStack.pop(); if(tempOper == '(') { break; } rightNum = numStack.pop(); leftNum = numStack.pop(); tempNum = opt(leftNum,tempOper,rightNum); numStack.push(tempNum); } status = 1; pos++; } else { if(operStack.empty()) { operStack.push(tempOper); status = 0; pos++; } else { tempOper2 = operStack.peek(); while (tempOper2 != '(' && !isGreater(tempOper,tempOper2)) { rightNum = numStack.pop(); leftNum = numStack.pop(); tempNum = opt(leftNum,tempOper2,rightNum); numStack.push(tempNum); operStack.pop(); if(operStack.empty()) { break; } tempOper2 = operStack.peek(); } operStack.push(tempOper); status = 0; pos++; } } break; case 2: //提取左括号( char oper = getOper(exp, pos); //如果获取到的不是左括号,则提示表达式输入不合法 if (oper != '(') { throw new IllegalArgumentException("Invalid expression:" + exp); } operStack.push(oper); //进入步骤0提取操作数,因为左括号后面紧跟的必须是操作数 status = 0; pos++; break; } } if(numStack.empty()) { throw new IllegalArgumentException("Invalid expression:" + exp); } tempNum = numStack.pop(); if(!numStack.empty()) { throw new IllegalArgumentException("Invalid expression:" + exp); } return tempNum; } }
相关推荐
数据结构试验,栈的应用,用栈计算表达式的值
结构清晰地介绍了用栈计算表达式的方法,希望像能对 和我一样入门级的朋友们有所帮助
利用栈实现表达式求值,可以计算加减乘除。留出接口,可以扩展。
问题描述:利用栈的基本操作实现一个算术表达式的求值的程序。 基本要求: (1) 定义栈的顺序存取结构...(3) 定义一个函数用来计算表达式结果,并且可以显示表达式的后缀表示。 (4) 设计一个测试主函数进行测试。
数据结构实验,基于栈实现表达式求值。本资源中包含C源代码以及完整的实验报告内容,并故有详细的程序说明。程序中有类似TC2.0的人机对话界面
java模拟栈实现表达式求值代码.zip可以完全实现多种功能的计算,采用了算符优先关系计算表达式的值。 注意:表达式的形式为 #表达式# 的形式,两个#号只表示表达式的开始和结束,真正的表达式在中间部分。。。。
数据结构课程实验设计,运用栈,计算四则运算的算术表达式,然后算出表达式的值
数据结构栈子系统(建栈,出进栈,计算表达式值,逆波兰式)
实验题目: 基于栈的算术表达式求值算法 实验环境: 学习完了数据结构第三章内容栈和队列 ...程序运行时,输入合法的算术表达式(中间值及最终结果要在0~9之间,可以包括加减乘除和括号),便可输出相应的计算结果。
用数据结构栈实现后缀表达式求值的问题 输入一个后缀表达式 可计算出它的值
关于数据结构栈的表达式实验报告,自己写的,可以参考一下的吧,可以输入小数进行计算
利用栈实现算术表达式的求值,表达式中可包含加+、减(负) -、乘*、除/、 乘方^、括号( )运算符,操作数可以为浮点数。 可采用直接求中缀表达式的方法, 也可采用先转换成后缀表达式后再求值的方法(参看课件) 。 ...
数据结构利用栈的两种方法计算表达式求值 c语言版 原本代码 可以直接下载运行 纯原创作 可满足数据结构作业或者实验报告 也可以熟悉栈的应用···
利用数栈和操作符栈,由中缀直接计算表达式的值
本程序利用两个栈——一个符号栈一个数字栈,实现了中缀表达式的计算,代码风格是C++,运行平台是QT,欢迎大家下载参考。
自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)
利用栈实现表达式求值,可供小学生作业练习,并给出评价
数据结构习题与解析(B级第3版) 李春葆 喻丹丹 编著 3.2
将中缀表达式转化为后缀表达式,再用栈计算
栈作中介,将表达式转化成逆波兰式,然后计算表达式的值。。支持括号。。允许负数和小数