package cn.mrlij.stack;
 
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * 使用數組實現棧
 *
 * @author dreamer
 *
 */
public class ArrayStackDemo {
  public static void main(String[] args) {
   String express = "5011+2*3-2";
   int index = 0;//定義一個索引值，用于遍歷表達式
    int num1 = 0;
    int num2 = 0;
    int res = 0;//計算結果
    char ch = ' ';
    int oper = 0;
    String keepNum = "";
    ArrayStack numStack = new ArrayStack(10);//創建一個數棧
    ArrayStack operStack = new ArrayStack(10);//創建一個符號棧
    while (true){
      ch = express.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;
        //處理多位數
        if(express.length()-1 == index){
          numStack.push(Integer.parseInt(keepNum));
        }else {
          if(operStack.isOper(express.substring(index+1,index+2).charAt(0))){
            numStack.push(Integer.parseInt(keepNum));
            keepNum = "";
          }
        }
        // numStack.push(ch-48);
      }
      index++;
      if(index >= express.length()){
        break;
      }
    }
    //掃描完之后，將數棧的值，與操作符中的值進行計算
    while (true){
      if(operStack.isEmpty()){
        break;
      }
      num1 = numStack.pop();
      num2 = numStack.pop();
      oper = operStack.pop();
      res = operStack.cal(num1,num2,oper);
      numStack.push(res);
    }
    System.out.println("表達式:"+express+"="+numStack.pop());
  }
}
 
class ArrayStack {
  private int MaxSize;// 定義數組的最大長度
  private int[] arr;// 定義數組，數據就放在該數組
  private int top = -1;// 定義棧頂，初始化數據為-1
 
  public ArrayStack(int maxSize) {
    this.MaxSize = maxSize;
    arr = new int[MaxSize];
  }
 
  // 判斷數組是否為空
  public boolean isEmpty() {
 
    return top == -1;
  }
 
  // 判斷數組是否滿了
  public boolean isFull() {
    //System.out.println("棧頂：" + top + "最大長度：" + MaxSize);
    return top == MaxSize - 1;
  }
  //取出棧頂元素
  public int peek(){
    return arr[top];
  }
  // 進棧
  public void push(int val) {
    // 先判斷棧是否滿了，滿了就不能添加進去
    if (isFull()) {
      System.out.println("棧已經滿了~~");
      return;
    }
    top++;
    arr[top] = val;
  }
 
  // 出棧
  public int pop() {
    // 先判斷棧是否為空
    if (isEmpty()) {
      throw new RuntimeException("棧為空，無法出棧！");
    }
    int val = arr[top];
    top--;
    return val;
  }
 
  public void show() {
    if (isEmpty()) {
      System.out.println("沒有數據");
      return;
    }
    for (int i = top; i >= 0; i--) {
      System.out.print(arr[i] + "\t");
    }
    System.out.println();
  }
 
  /**
   * 判斷是否是一個操作符
   * @param oper 傳入的字符
   * @return 如是操作符返回true，否則返回false
   */
  public boolean isOper(char oper){
    return oper == '+' || oper == '-' || oper =='*' || oper == '/';
  }
 
  /**
   * 判斷操作符的優先級
   * @param oper 傳入的優先級
   * @return 返回優先級 分別是1,-1,0
   */
  public int priority(int oper ){
    if(oper == '*' || oper == '/'){
      return 1;
    } else if(oper == '+' || oper == '-'){
      return 0;
    }else {
      return -1;
    }
  }
 
  //計算方法
  public int cal(int num1,int num2,int oper){
    int res = 0;
    switch (oper){
      case '+': res = num1 + num2;
      break;
      case '-': res = num2 - num1;
      break;
      case '*': res = num1 * num2;
      break;
      case '/': res = num2 /num1;
    }
    return res;
  }
}