文章目录

1.栈实现计算器（中缀表达式）1.1流程图1.2 代码实现 2. 逆波兰(后缀)表达式实现2.1 初步实现2.2 中缀表达式转后缀表达式2.2.1步骤2.2.2 代码实现

1.栈实现计算器（中缀表达式）

1.1流程图

1.2 代码实现

public class Calculator { public static void main(String[] args) { String expression = "700*2*2-5+1-5+3-4"; //创建数栈和运算符栈 ArrayStackCal numStack = new ArrayStackCal(10); ArrayStackCal operStack = new ArrayStackCal(10); int index = 0;//用于扫描 int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch = ' '; //将扫描结果保存到ch String keepNum = "";//用于拼接字符串 while (true){ //遍历表达式将字符保存到ch ch = expression.substring(index,index+1).charAt(0); //判断是否为运算符 if (operStack.isOper(ch)) { if (!operStack.isEmpty()){ if (operStack.priority(ch) <= operStack.priority(operStack.peek())) { //运算优先级小于栈顶时计算 num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = operStack.cal(num1, num2, oper); //将运算结果入数栈 numStack.push(res); //将当前操作符入符号栈 operStack.push(ch); } else { //运算优先级大于栈顶时入符号栈 operStack.push(ch); } }else { //如果为空直接入栈 operStack.push(ch); } }else { //如果下一位还是数字就拼接 keepNum += ch; //如果ch已经是expression的最后一位，就直接入栈 if (index == expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); }else{ //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈 //注意是看后一位，不是index++ if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) { //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123" numStack.push(Integer.parseInt(keepNum)); //重要的!!!!!!, keepNum清空 keepNum = ""; } } } index++; if (index>=expression.length()){ break; } } //当表达式遍历完，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行 while (true){ if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = operStack.cal(num1,num2,oper); numStack.push(res); } int res2 = numStack.pop(); System.out.println("表达式"+expression+"="+res2); } } //继承ArrayStack用数组实现栈 class ArrayStackCal extends ArrayStack{ public ArrayStackCal() { } public ArrayStackCal(int maxSize) { super(maxSize); } /** * 返回运算符的优先级，用数字表示 * @param oper * @return */ public int priority(int oper){ if (oper=='*'||oper=='/'){ return 1; }else if (oper=='+' || oper=='-'){ return 0; }else { return -1; } } /** * 判断是否是一个运算符 * @param val * @return */ public boolean isOper(char val){ return val =='+' ||val =='-' || val =='*'|| val =='/'; } /** * 返回计算结果 * @param num1 * @param num2 * @param oper * @return */ public int cal(int num1,int num2,int oper){ int res = 0;//计算结果 switch (oper){ case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } return res; } }

ArrayStack

class ArrayStack implements Stack1{ public int maxSize;//栈的最大长度 public int[] stack; public int top = -1;//栈顶 public ArrayStack() { } public ArrayStack(int maxSize) { this.maxSize = maxSize; stack=new int[this.maxSize]; } @Override public int getSize() { return stack.length; } @Override public boolean isEmpty() { return top==-1; } @Override public void push(int value) { if (isFull()){ System.out.println("栈满！"); return; } top++; stack[top]=value; } public boolean isFull(){ return top==maxSize-1; } @Override public int pop() { if (isEmpty()){ throw new RuntimeException("栈空，无法取出数据！"); } int value = stack[top]; top--; return value; } @Override public int peek() { //返回栈顶的值 return stack[top]; } public void traverse(){ if (isEmpty()){ System.out.println("栈空，无法取出数据！"); return; } for (int i = top; i >=0 ; i--) { System.out.println("stack["+i+"]"+"="+stack[i]); } } }

stack1

public interface Stack1 { int getSize(); boolean isEmpty(); void push(int e); int pop(); int peek(); }

2. 逆波兰(后缀)表达式实现

例如：(3+4)X5-6对应的后缀表达式就是，针对后缀表达式求值步骤如下: 1.从左至右扫描，将3和4压入堆栈; 2.遇到+运算符，因此弹出4和3 (4为栈顶元素，3为次顶元素)，计算出3+4的值，得7，再将7入栈; 3.将5入栈; 4.接下来是X运算符，因此弹出5和7,计算出7X5=35,将35入栈; 5.将6入栈; 6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果

2.1 初步实现

实现思路

定义表达式

将表达式按空格分割放入列表

计算结果 ：从左到右扫描，扫到的是数字就入栈，符号就pop出两个数字然后进行运算，再将结果入栈循环执行。直到最后还在栈中的元素就是结果。

返回结果

//逆波兰表达式的计算 public class PolanNotation { public static void main(String[] args) { //定义逆波兰表达式 String expression = "3 4 + 5 * 6 -"; ArrayList<String> list = getListString(expression); System.out.println(list); int cal = cal(list); System.out.println(cal); } /** * 将表达式放入ArrayList中 * @param expression * @return */ public static ArrayList<String> getListString(String expression){ //将表达式按空格分割 String[] s = expression.split(" "); ArrayList<String> list = new ArrayList<>(); //将表达式放入ArrayList中 for (String s1 : s) { list.add(s1); } return list; } public static int cal(ArrayList<String> list){ Stack<String> stack = new Stack<>(); int num1 = 0; int num2 = 0; int res = 0;//存放运算结果 for (String s : list) { //用正则表达式取出数 if(s.matches("\\d+")){//匹配的是多位数 stack.push(s); }else { num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); switch (s){ case "+": res = num2+num1; break; case "-": res = num2-num1; break; case "*": res = num2*num1; break; case "/": res = num2/num1; break; default: throw new RuntimeException("运算符有误"); } //将计算结果入栈 stack.push(""+res); } } //返回栈中最后剩下的元素 return Integer.parseInt(stack.pop()); } }

这里表达式是后缀表达式，下面添加中缀转后缀表达式的实现。

2.2 中缀表达式转后缀表达式

2.2.1步骤

1)初始化两个栈:运算符栈s1和储存中间结果的栈s2; 2)从左至右扫描中缀表达式; . 3)遇到操作数时，将其压s2; 4)遇到运算符时，比较其与s1栈顶运算符的优先级: 1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈; 2.否则，若优先级比栈顶运算符的高，也将运算符压入s1; 3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较; 5)遇到括号时: (1) 如果是左括号“(”，则直接压入s1 (2)如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 6)重复步骤2至5，直到表达式的最右边 7)将s1中剩余的运算符依次弹出并压入s2 8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例 1+((2+3)X4)-5

扫描到的元素s2 (栈底->栈顶)s1(栈底->栈顶)说明11空数字，入栈s2+1+s1为空，入栈s1(1+ (左括号，入栈s1(1+ ( (左括号，入栈s121 2+ ( (数字，入栈s2+1 2+ ( ( +s1栈顶为左括号 ，入栈s131 2 3+ ( ( +数字，入栈s2)1 2 3 ++ (右括号，弹出运算符直到遇到左括号*1 2 3 ++ ( *s1栈顶为左括号，入栈s141 2 3 + 4+ ( *数字，入栈s2)1 2 3 + 4 *+右括号，弹出运算符直到遇到左括号-1 2 3 + 4 * +--与+优先级相同，弹出+，压入-51 2 3 + 4 * + 5-数字，入栈s2扫描结束1 2 3 + 4 * + 5 -空s1剩余运算符压入s2

2.2.2 代码实现

//逆波兰表达式的计算 public class PolanNotation { public static void main(String[] args) { String expression2 = "1+((2+3)*4)-5"; //将中缀表达式放入集合 List<String> list1 = toInfixExpressionList(expression2); System.out.println("转换前"+list1); //将中缀表达式转为后缀表达式 List<String> list2 = parseSuffixExpreesionList(list1); System.out.println("转换后"+list2); int res = cal(list2); System.out.println(expression2+"="+res); // //定义逆波兰表达式 // String expression = "3 4 + 5 * 6 -"; // ArrayList<String> list = getListString(expression); // System.out.println(list); // int cal = cal(list); // System.out.println(cal); } /** * 将中缀表达式转为后缀表达式 * @param list * @return */ public static List<String> parseSuffixExpreesionList(List<String> list){ Stack<String> s1 = new Stack<>();//存放运算符 List<String> s2 = new ArrayList<>();//存放中间结果 for (String s : list) { if (s.matches("\\d+")){ //遇到操作数时，将其放入s2; s2.add(s); }else if(s.equals("(")) { //如果是左括号“(”，则直接压入s1 s1.push(s); }else if(s.equals(")")){ //)如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop();//丢弃左括号 }else { //如果是运算符，判断优先级 while (s1.size()!=0 && Operation.getValue(s1.peek())>= Operation.getValue(s)){ //若当前运算符优先级小于等于栈顶元素将s1栈顶的运算符弹出并放入到s2中，再次循环判断 s2.add(s1.pop()); } //其他情况， 如果s1为空，或栈顶运算符为左括号“(”，优先级比栈顶运算符的高，入栈 s1.push(s); } } //将s1中剩余的运算符依次弹出放入s2 while (s1.size() !=0){ s2.add(s1.pop()); } return s2; } /** * 将中缀表达式放入集合 * @param s * @return */ public static List<String> toInfixExpressionList(String s){ List<String> list = new ArrayList<>(); String str;//拼接字符串 char c ;//存放遍历的字符 int i=0; //用于遍历字符串 do { if ((c=s.charAt(i))<48||(c=s.charAt(i))>57){//当c为运算符时 list.add(""+c); i++; }else {//当c为一个数时 str="";//将str置空 while (i<s.length() && (c=s.charAt(i))>=48 &&(c=s.charAt(i))<=57){ str+=c; i++; } list.add(str); } }while (i < s.length()); return list; } /** * 将后缀表达式放入ArrayList中 * @param expression * @return */ public static List<String> getListString(String expression){ //将表达式按空格分割 String[] s = expression.split(" "); List<String> list = new ArrayList<>(); //将表达式放入ArrayList中 for (String s1 : s) { list.add(s1); } return list; } public static int cal(List<String> list){ Stack<String> stack = new Stack<>(); int num1 = 0; int num2 = 0; int res = 0;//存放运算结果 for (String s : list) { //用正则表达式取出数 if(s.matches("\\d+")){//匹配的是多位数 stack.push(s); }else { num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); switch (s){ case "+": res = num2+num1; break; case "-": res = num2-num1; break; case "*": res = num2*num1; break; case "/": res = num2/num1; break; default: throw new RuntimeException("运算符有误"); } //将计算结果入栈 stack.push(""+res); } } //返回栈中最后剩下的元素 return Integer.parseInt(stack.pop()); } } //编写一个类 Operation 可以返回一个运算符 对应的优先级 class Operation { private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; //写一个方法，返回对应的优先级数字 public static int getValue(String operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: break; } return result; } }