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;
  }
}