package cn.mrlij.stack;
 
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * 使用數(shù)組實(shí)現(xiàn)棧
 *
 * @author dreamer
 *
 */
public class ArrayStackDemo {
  public static void main(String[] args) {
   String express = "5011+2*3-2";
   int index = 0;//定義一個(gè)索引值，用于遍歷表達(dá)式
    int num1 = 0;
    int num2 = 0;
    int res = 0;//計(jì)算結(jié)果
    char ch = ' ';
    int oper = 0;
    String keepNum = "";
    ArrayStack numStack = new ArrayStack(10);//創(chuàng)建一個(gè)數(shù)棧
    ArrayStack operStack = new ArrayStack(10);//創(chuàng)建一個(gè)符號(hào)棧
    while (true){
      ch = express.substring(index,index+1).charAt(0);//不停的遍歷操作符
      //判斷是否是操作符
      if (operStack.isOper(ch)){
        //判斷當(dāng)前符號(hào)棧是否有符號(hào)存在
        if(!operStack.isEmpty()){
          //不為空則判斷優(yōu)先級(jí)
          if(operStack.priority(ch)<=operStack.priority(operStack.peek())){
            //當(dāng)優(yōu)先級(jí)小于棧頂?shù)闹禃r(shí)候，彈出兩個(gè)數(shù)棧的值進(jìn)行計(jì)算
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = operStack.cal(num1,num2,oper);
            //計(jì)算以后將計(jì)算得到的值放入數(shù)棧
            numStack.push(res);
            //同時(shí)將此時(shí)的操作符放入符號(hào)棧
            operStack.push(ch);
          }else{
            //優(yōu)先級(jí)
            operStack.push(ch);
          }
        }else{
          //為空直接將符號(hào)入棧
          operStack.push(ch);
        }
      }else {
        keepNum += ch;
        //處理多位數(shù)
        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;
      }
    }
    //掃描完之后，將數(shù)棧的值，與操作符中的值進(jìn)行計(jì)算
    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("表達(dá)式:"+express+"="+numStack.pop());
  }
}
 
class ArrayStack {
  private int MaxSize;// 定義數(shù)組的最大長度
  private int[] arr;// 定義數(shù)組，數(shù)據(jù)就放在該數(shù)組
  private int top = -1;// 定義棧頂，初始化數(shù)據(jù)為-1
 
  public ArrayStack(int maxSize) {
    this.MaxSize = maxSize;
    arr = new int[MaxSize];
  }
 
  // 判斷數(shù)組是否為空
  public boolean isEmpty() {
 
    return top == -1;
  }
 
  // 判斷數(shù)組是否滿了
  public boolean isFull() {
    //System.out.println("棧頂：" + top + "最大長度：" + MaxSize);
    return top == MaxSize - 1;
  }
  //取出棧頂元素
  public int peek(){
    return arr[top];
  }
  // 進(jìn)棧
  public void push(int val) {
    // 先判斷棧是否滿了，滿了就不能添加進(jìn)去
    if (isFull()) {
      System.out.println("棧已經(jīng)滿了~~");
      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("沒有數(shù)據(jù)");
      return;
    }
    for (int i = top; i >= 0; i--) {
      System.out.print(arr[i] + "\t");
    }
    System.out.println();
  }
 
  /**
   * 判斷是否是一個(gè)操作符
   * @param oper 傳入的字符
   * @return 如是操作符返回true，否則返回false
   */
  public boolean isOper(char oper){
    return oper == '+' || oper == '-' || oper =='*' || oper == '/';
  }
 
  /**
   * 判斷操作符的優(yōu)先級(jí)
   * @param oper 傳入的優(yōu)先級(jí)
   * @return 返回優(yōu)先級(jí) 分別是1,-1,0
   */
  public int priority(int oper ){
    if(oper == '*' || oper == '/'){
      return 1;
    } else if(oper == '+' || oper == '-'){
      return 0;
    }else {
      return -1;
    }
  }
 
  //計(jì)算方法
  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;
  }
}