文章目錄

• 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 = ' '; //將掃描結果保存到chString keepNum = "";//用于拼接字符串while (true){//遍歷表達式將字符保存到chch = 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];}@Overridepublic int getSize() {return stack.length;}@Overridepublic boolean isEmpty() {return top==-1;}@Overridepublic void push(int value) {if (isFull()){System.out.println("棧滿！");return;}top++;stack[top]=value;}public boolean isFull(){return top==maxSize-1;}@Overridepublic int pop() {if (isEmpty()){throw new RuntimeException("棧空，無法取出數據！");}int value = stack[top];top--;return value;}@Overridepublic 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(棧底->棧頂)說明

1	1	空	數字，入棧s2
+	1	+	s1為空，入棧s1
(	1	+ (	左括號，入棧s1
(	1	+ ( (	左括號，入棧s1
2	1 2	+ ( (	數字，入棧s2
+	1 2	+ ( ( +	s1棧頂為左括號 ，入棧s1
3	1 2 3	+ ( ( +	數字，入棧s2
)	1 2 3 +	+ (	右括號，彈出運算符直到遇到左括號
*	1 2 3 +	+ ( *	s1棧頂為左括號，入棧s1
4	1 2 3 + 4	+ ( *	數字，入棧s2
)	1 2 3 + 4 *	+	右括號，彈出運算符直到遇到左括號
-	1 2 3 + 4 * +	-	-與+優先級相同，彈出+，壓入-
5	1 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("(")) {//如果是左括號“(”，則直接壓入s1s1.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中剩余的運算符依次彈出放入s2while (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;}}

總結

以上是生活随笔為你收集整理的（数据结构与算法）使用栈来实现综合计算器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。