运用数据结构实现计算器

先说说我实现的思想首先把复杂问题简单化，先考虑没有括号但是表达式是连续的情况运算符当中‘*’和‘/’具有相同优先级而且是最高优先级，而'+'和'-'有相同优先级并次于乘除把复杂的问题简单化，就像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][+]第七步：栈一 [[][(]栈二 [#][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(); // 用于存储和处理操作数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<String> tempExpression = new ArrayList<String>();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();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("[\\d{1}]")) {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;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<Object> ls = new ArrayList<Object>();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结果：3+2*3result:9----------------5*3*9result:135----------------3*2+135-5result:136----------------136/2result:68----------------The result is 68这个程序稳定性先不说，因为主要矛盾不是这个，我们的目的是学习数据结构。