2022年运用数据结构实现 .pdf
先说说我实现的思想首先把复杂问题简单化，先考虑没有括号但是表达式是连续的情况运算符当中*和/具有相同优先级而且是最高优先级，而+和-有相同优先级并次于乘除把复杂的问题简单化，就像cpu 只有加法器，所有的运算都转换为加法运算，这里我也是这样想的首先让字符串入栈，情况如下：我用 表示一个元素例如：3+2*3 3+2*3 栈顶出栈（在不考虑字符串不合法的情况下第一个出栈的一定是操作数）后面紧跟的是运算符第一步：出栈得到数据 3 栈内 3+2*第二步：出栈得运算符 *栈内 3+2 第三步：判断到运算符是*第四步：出栈得到数据 2 栈内 3+第五步：计算 3*2=6 入栈 6 栈内 3+6 第六步：栈内元素累加的结果：3+6=9 现在来考虑有括号的情况：例如：3+(2+4*3)我用两个栈，第一个栈用来存放括号，第二个用来存放数第一步：栈一 栈二#号用于标记第二步：栈一 栈而#3 第三步：栈一 栈二#3+第四步：栈一(栈二#3+#第五步：栈一(栈二#3+#2 第六步：栈一(栈二#3+#2+第七步：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -栈一(栈二#3+#2+4 第八步：栈一(栈二#3+#2+4*第九步：栈一(栈二#3+#2+4*3 第十步：由于发现括号匹配所以栈一出栈栈一 以“#”号为标记得到一个连续的没有括号的运算式2+4*3 计算得到结果 14 然后再压入栈二栈二#3+12 第十一步：由于发现括号匹配所以栈一出栈栈一 空以“#”号为标记得到一个连续的没有括号的运算式3+12 计算得到结果 15 压入栈二第十二步：发现栈一为空计算完毕栈二弹出得到结果 15 代码如下：import java.util.*;public class Calculator public static boolean machesBrackets(String expression1,String expression2)if(expression1.equals()&expression2.equals()return true;else if(expression1.equals()&expression2.equals()return true;else if(expression1.equals()&expression2.equals()return true;else return false;public static void main(String args)Scanner input=new Scanner(System.in);System.out.println(请输入预算表达式);String expression=input.next();expression=+expression+;/这样的目的是当用户输入的表达式最外是数字而非括号时，为了每个数都能入栈，所以添加对括号在外面 SimpleCalculator scct=new SimpleCalculator();/用于处理连续的没有括号的数学表达式 Stack stack1=new Stack();/用于匹配括号 Stack stack2=new Stack();/用于存储和处理操作数名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -String bracket=;/存储括号的临时变量 String regex=()1;String temp=;stack2.push(#);/向栈 2 压入标志 for(int i=0;i expression.length();i+)if(bracket=expression.charAt(i)+).matches(regex)/如果是括号 if(!stack1.isEmpty()String bkt=stack1.getTop().toString();/栈 1 弹出栈顶元素得到准备匹配的括号 if(Calculator.machesBrackets(bkt,bracket)/如果匹配成功 stack1.pop();/栈顶出栈 String str=;if(!stack2.isEmpty()/如果栈 2 不为空 String exp=;List tempExpression=new ArrayList();while(!(str=stack2.pop().toString()/若不是结束标记 .equals(#)tempExpression.add(str);for(int j=tempExpression.size()-1;j=0;j-)exp+=tempExpression.get(j);tempExpression=null;System.out.println(exp);/调试语句 Integer result=scct.calculate(exp);/计算出结果 System.out.println(result:+result);/调试语句 System.out.println(-);/调试语句 stack2.push(result.toString();/将计算结果压入栈2 else /如果匹配不成功 stack1.push(bracket);/将括 号压入栈顶 stack2.push(#);/向栈 2 压入标志 /ds.push(stack1,expression.charAt(i)+);else stack1.push(expression.charAt(i)+);else /如果是操作数或者运算符 temp=expression.charAt(i)+;stack2.push(temp);System.out.println(The result is +stack2.pop();class SimpleCalculator public int calculate(String expression)Stack stack1=new Stack();名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -Stack stack2=new Stack();Stack tempStack=new Stack();String d=;if(expression.charAt(0)=-)/如果表达式第一个是负号 expression=0+expression;for(int i=0;i expression.length();i+)String c=expression.charAt(i)+;if(c.matches(d1)d+=c;else stack1.push(d);/运算数入栈 stack1.push(c);/运算符入栈 d=;stack1.push(d);/最后一个操作数入栈 int temp1=0;/暂存第一个操作数 int temp2=0;/暂存第二个操作数 String sign=;/暂存操作符 while(!stack1.isEmpty()/如果栈 1 不为空 temp1=Integer.parseInt(stack1.pop().toString();/栈 1 出栈 得到第一个运算数 sign=(String)stack1.pop();/栈 1 出栈 得到运算符 int result=0;/用于存储每次运算的结果 if(sign=null)/如果没有取到操作符,说明是最后一个操作数 stack2.push(temp1);break;else if(sign.equals(*)/如果为乘法 temp2=Integer.parseInt(stack1.pop().toString();/栈 1 出栈 /得到第二个操作数 result=temp1*temp2;stack1.push(result);/将预算结果压入栈1 else if(sign.equals(/)/如果为除法 temp2=Integer.parseInt(stack1.pop().toString();/栈 1 出栈 /得到第二个操作数 tempStack.push(temp1);tempStack.push(temp2);while(!stack1.isEmpty()&stack1.getTop().equals(/)stack1.pop();/运算符出栈 tempStack.push(stack1.pop();/运算数出栈，并压入临时栈 result=Integer.parseInt(tempStack.pop().toString();while(!tempStack.isEmpty()temp1=Integer.parseInt(tempStack.pop().toString();result=result/temp1;stack1.push(result);/将预算结果压入栈1 else if(sign.equals(-)/如果为加减法 temp1=-temp1;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -stack2.push(temp1);else /如果是加法 stack2.push(temp1);/现在栈 2 的操作数全部是加法的操作数，那么只要对栈2 的操作数累加即可得到运算结果 int result=0;while(!stack2.isEmpty()Integer temp=(Integer)stack2.pop();result+=temp;return result;class Stack List ls=new ArrayList();public Object pop()/出栈 if(!this.isEmpty()Object data=ls.get(ls.size()-1);ls.remove(ls.size()-1);return data;return null;/如果栈为空 public void push(Object data)/压栈 ls.add(data);public Object getTop()/获取栈顶元素 if(!this.isEmpty()return ls.get(ls.size()-1);return null;/如果栈为空 public boolean isEmpty()/判断栈是否为空 if(ls.size()=0)return true;return false;输入：3*2+(5*3*(3+2*3)-5/2 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -结果：3+2*3 result:9-5*3*9 result:135-3*2+135-5 result:136-136/2 result:68-The result is 68 这个程序稳定性先不说，因为主要矛盾不是这个，我们的目的是学习数据结构。但是我觉得该算法肯定有很多不好的地方，我很希望有人能指出来，并给予指点！名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -
