package com.hsy.stack;

public class Calculator {

? ? public static void main(String[] args) {
? ? ? ? //根據前面老師思路，完成表達式的運算
? ? ? ? String expression = "7*2+100-5+3-4/2";//如何處理多位數的問題？
? ? ? ? //創(chuàng)建兩個棧，數棧，一個符號棧
? ? ? ? ArrayStack2 numStack = new ArrayStack2(10);
? ? ? ? ArrayStack2 operStack = new ArrayStack2(10);
? ? ? ? //定義需要的相關變量
? ? ? ? int index = 0;//用于掃描
? ? ? ? int num1 = 0;
? ? ? ? int num2 = 0;
? ? ? ? int oper = 0;
? ? ? ? int res = 0;
? ? ? ? char ch = ' '; //將每次掃描得到char保存到ch
? ? ? ? String keepNum = ""; //用于拼接 多位數
? ? ? ? //開始while循環(huán)的掃描expression
? ? ? ? while(true) {
? ? ? ? ? ? //依次得到expression 的每一個字符
? ? ? ? ? ? ch = expression.substring(index, index+1).charAt(0);
? ? ? ? ? ? //判斷ch是什么，然后做相應的處理
? ? ? ? ? ? if(operStack.isOper(ch)) {//如果是運算符
? ? ? ? ? ? ? ? //判斷當前的符號棧是否為空
? ? ? ? ? ? ? ? if(!operStack.isEmpty()) {
? ? ? ? ? ? ? ? ? ? //如果符號棧有操作符，就進行比較,如果當前的操作符的優(yōu)先級小于或者等于棧中的操作符,就需要從數棧中pop出兩個數,
? ? ? ? ? ? ? ? ? ? //在從符號棧中pop出一個符號，進行運算，將得到結果，入數棧，然后將當前的操作符入符號棧
? ? ? ? ? ? ? ? ? ? if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
? ? ? ? ? ? ? ? ? ? ? ? num1 = numStack.pop();
? ? ? ? ? ? ? ? ? ? ? ? num2 = numStack.pop();
? ? ? ? ? ? ? ? ? ? ? ? oper = operStack.pop();
? ? ? ? ? ? ? ? ? ? ? ? res = numStack.cal(num1, num2, oper);
? ? ? ? ? ? ? ? ? ? ? ? //把運算的結果如數棧
? ? ? ? ? ? ? ? ? ? ? ? numStack.push(res);
? ? ? ? ? ? ? ? ? ? ? ? //然后將當前的操作符入符號棧
? ? ? ? ? ? ? ? ? ? ? ? operStack.push(ch);
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? //如果當前的操作符的優(yōu)先級大于棧中的操作符， 就直接入符號棧.
? ? ? ? ? ? ? ? ? ? ? ? operStack.push(ch);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? //如果為空直接入符號棧..
? ? ? ? ? ? ? ? ? ? operStack.push(ch); // 1 + 3
? ? ? ? ? ? ? ? }
? ? ? ? ? ? } else { //如果是數，則直接入數棧

? ? ? ? ? ? ? ? //numStack.push(ch - 48); //? "1+3" '1' => 1
? ? ? ? ? ? ? ? //分析思路
? ? ? ? ? ? ? ? //1. 當處理多位數時，不能發(fā)現是一個數就立即入棧，因為他可能是多位數
? ? ? ? ? ? ? ? //2. 在處理數，需要向expression的表達式的index 后再看一位,如果是數就進行掃描，如果是符號才入棧
? ? ? ? ? ? ? ? //3. 因此我們需要定義一個變量 字符串，用于拼接

? ? ? ? ? ? ? ? //處理多位數
? ? ? ? ? ? ? ? keepNum += ch;

? ? ? ? ? ? ? ? //如果ch已經是expression的最后一位，就直接入棧
? ? ? ? ? ? ? ? if (index == expression.length() - 1) {
? ? ? ? ? ? ? ? ? ? numStack.push(Integer.parseInt(keepNum));
? ? ? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? ? ? //判斷下一個字符是不是數字，如果是數字，就繼續(xù)掃描，如果是運算符，則入棧
? ? ? ? ? ? ? ? ? ? //注意是看后一位，不是index++
? ? ? ? ? ? ? ? ? ? if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
? ? ? ? ? ? ? ? ? ? ? ? //如果后一位是運算符，則入棧 keepNum = "1" 或者 "123"
? ? ? ? ? ? ? ? ? ? ? ? numStack.push(Integer.parseInt(keepNum));
? ? ? ? ? ? ? ? ? ? ? ? //重要的!!!!!!, keepNum清空
? ? ? ? ? ? ? ? ? ? ? ? keepNum = "";

? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? //讓index + 1, 并判斷是否掃描到expression最后.
? ? ? ? ? ? index++;
? ? ? ? ? ? if (index >= expression.length()) {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? //當表達式掃描完畢，就順序的從 數棧和符號棧中pop出相應的數和符號，并運行.
? ? ? ? while(true) {
? ? ? ? ? ? //如果符號棧為空，則計算到最后的結果, 數棧中只有一個數字【結果】
? ? ? ? ? ? if(operStack.isEmpty()) {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? num1 = numStack.pop();
? ? ? ? ? ? num2 = numStack.pop();
? ? ? ? ? ? oper = operStack.pop();
? ? ? ? ? ? res = numStack.cal(num1, num2, oper);
? ? ? ? ? ? numStack.push(res);//入棧
? ? ? ? }
? ? ? ? //將數棧的最后數，pop出，就是結果
? ? ? ? int res2 = numStack.pop();
? ? ? ? System.out.printf("表達式 %s = %d", expression, res2);
? ? }

}

//先創(chuàng)建一個棧,直接使用前面創(chuàng)建好
//定義一個 ArrayStack2 表示棧, 需要擴展功能
class ArrayStack2 {
? ? private int maxSize; // 棧的大小
? ? private int[] stack; // 數組，數組模擬棧，數據就放在該數組
? ? private int top = -1;// top表示棧頂，初始化為-1

? ? //構造器
? ? public ArrayStack2(int maxSize) {
? ? ? ? this.maxSize = maxSize;
? ? ? ? stack = new int[this.maxSize];
? ? }

? ? //增加一個方法，可以返回當前棧頂的值, 但是不是真正的pop
? ? public int peek() {
? ? ? ? return stack[top];
? ? }

? ? //棧滿
? ? public boolean isFull() {
? ? ? ? return top == maxSize - 1;
? ? }
? ? //棧空
? ? public boolean isEmpty() {
? ? ? ? return top == -1;
? ? }
? ? //入棧-push
? ? public void push(int value) {
? ? ? ? //先判斷棧是否滿
? ? ? ? if(isFull()) {
? ? ? ? ? ? System.out.println("棧滿");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? top++;
? ? ? ? stack[top] = value;
? ? }
? ? //出棧-pop, 將棧頂的數據返回
? ? public int pop() {
? ? ? ? //先判斷棧是否空
? ? ? ? if(isEmpty()) {
? ? ? ? ? ? //拋出異常
? ? ? ? ? ? throw new RuntimeException("?？?，沒有數據~");
? ? ? ? }
? ? ? ? int value = stack[top];
? ? ? ? top--;
? ? ? ? return value;
? ? }
? ? //顯示棧的情況[遍歷棧]， 遍歷時，需要從棧頂開始顯示數據
? ? public void list() {
? ? ? ? if(isEmpty()) {
? ? ? ? ? ? System.out.println("棧空，沒有數據~~");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? //需要從棧頂開始顯示數據
? ? ? ? for(int i = top; i >= 0 ; i--) {
? ? ? ? ? ? System.out.printf("stack[%d]=%d\n", i, stack[i]);
? ? ? ? }
? ? }
? ? //返回運算符的優(yōu)先級，優(yōu)先級是程序員來確定, 優(yōu)先級使用數字表示
? ? //數字越大，則優(yōu)先級就越高.
? ? public int priority(int oper) {
? ? ? ? if(oper == '*' || oper == '/'){
? ? ? ? ? ? return 1;
? ? ? ? } else if (oper == '+' || oper == '-') {
? ? ? ? ? ? return 0;
? ? ? ? } else {
? ? ? ? ? ? return -1; // 假定目前的表達式只有 +, - , * , /
? ? ? ? }
? ? }
? ? //判斷是不是一個運算符
? ? public boolean isOper(char val) {
? ? ? ? return val == '+' || val == '-' || val == '*' || val == '/';
? ? }
? ? //計算方法
? ? public int cal(int num1, int num2, int oper) {
? ? ? ? int res = 0; // res 用于存放計算的結果
? ? ? ? switch (oper) {
? ? ? ? ? ? case '+':
? ? ? ? ? ? ? ? res = num1 + num2;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case '-':
? ? ? ? ? ? ? ? res = num2 - num1;// 注意順序
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case '*':
? ? ? ? ? ? ? ? res = num1 * num2;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case '/':
? ? ? ? ? ? ? ? res = num2 / num1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? default:
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? return res;
? ? }

}