package com.hsy.stack;

public class Calculator {

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

? ? ? ? ? ? ? ? //numStack.push(ch - 48); //? "1+3" '1' => 1
? ? ? ? ? ? ? ? //分析思路
? ? ? ? ? ? ? ? //1. 當(dāng)處理多位數(shù)時，不能發(fā)現(xiàn)是一個數(shù)就立即入棧，因?yàn)樗赡苁嵌辔粩?shù)
? ? ? ? ? ? ? ? //2. 在處理數(shù)，需要向expression的表達(dá)式的index 后再看一位,如果是數(shù)就進(jìn)行掃描，如果是符號才入棧
? ? ? ? ? ? ? ? //3. 因此我們需要定義一個變量 字符串，用于拼接

? ? ? ? ? ? ? ? //處理多位數(shù)
? ? ? ? ? ? ? ? keepNum += ch;

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

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

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

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

}

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

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

? ? //增加一個方法，可以返回當(dāng)前棧頂?shù)闹? 但是不是真正的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, 將棧頂?shù)臄?shù)據(jù)返回
? ? public int pop() {
? ? ? ? //先判斷棧是否空
? ? ? ? if(isEmpty()) {
? ? ? ? ? ? //拋出異常
? ? ? ? ? ? throw new RuntimeException("?？眨瑳]有數(shù)據(jù)~");
? ? ? ? }
? ? ? ? int value = stack[top];
? ? ? ? top--;
? ? ? ? return value;
? ? }
? ? //顯示棧的情況[遍歷棧]， 遍歷時，需要從棧頂開始顯示數(shù)據(jù)
? ? public void list() {
? ? ? ? if(isEmpty()) {
? ? ? ? ? ? System.out.println("?？?，沒有數(shù)據(jù)~~");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? //需要從棧頂開始顯示數(shù)據(jù)
? ? ? ? for(int i = top; i >= 0 ; i--) {
? ? ? ? ? ? System.out.printf("stack[%d]=%d\n", i, stack[i]);
? ? ? ? }
? ? }
? ? //返回運(yùn)算符的優(yōu)先級，優(yōu)先級是程序員來確定, 優(yōu)先級使用數(shù)字表示
? ? //數(shù)字越大，則優(yōu)先級就越高.
? ? public int priority(int oper) {
? ? ? ? if(oper == '*' || oper == '/'){
? ? ? ? ? ? return 1;
? ? ? ? } else if (oper == '+' || oper == '-') {
? ? ? ? ? ? return 0;
? ? ? ? } else {
? ? ? ? ? ? return -1; // 假定目前的表達(dá)式只有 +, - , * , /
? ? ? ? }
? ? }
? ? //判斷是不是一個運(yùn)算符
? ? public boolean isOper(char val) {
? ? ? ? return val == '+' || val == '-' || val == '*' || val == '/';
? ? }
? ? //計算方法
? ? public int cal(int num1, int num2, int oper) {
? ? ? ? int res = 0; // res 用于存放計算的結(jié)果
? ? ? ? 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;
? ? }

}