[数据结构与算法]单向链表构建的栈和字符串计算器

栈：

public class StackAsLinked<TT> {
    int size=10;
    Node1 back;
    Node1 fanhui;
    Node1 n0=new Node1 ( null );
    int count=0;


    public static void main ( String[] args ) {
        StackAsLinked s2 = new StackAsLinked ();
        Scanner s1 = new Scanner ( System.in );
        while ( true ) {
            System.out.println ( "push" );
            System.out.println ( "pop" );
            System.out.println ( "show" );
            System.out.println ( "exit" );
            String str = s1.next ( );
            switch ( str ) {
                case "p":
                    System.out.println ( "请输入要存的数" );
                    s2.push ( s1.nextInt ( ) );
                    break;
                case "po":
                    s2.pop ( );
                    System.out.println ("删除成功" );
                    break;
                case "s":
                    s2.show ( );
                    break;
                case "e":
                    s1.close ();
                    System.out.println ("退出成功" );
                    System.exit ( 0 );
            }

        }
    }




    public void push(TT i){
        if(isfull ()){
            System.out.println ("满了" );
            return;
        }else {
            Node1 nn = new Node1 ( i );
            nn.next=n0.next;
            n0.next = nn;
            count++;
            back=nn;
        }
    }

    public TT pop(){
        if(isEmpty ()){
            System.out.println ("空了" );
           return null;
        }else{
            fanhui=n0.next;
            n0.next=n0.next.next;
            count--;
            return fanhui.no;
        }

    }
    public void show(){
        Node1 temp=n0.next;
        if(isEmpty ()){
            System.out.println ("空了" );
            return;
        }else{
            while ( true ) {
                System.out.println (" "+temp.no );
                temp =temp.next;
                if(temp==null)
                    break;
            }
        }
    }

    public boolean isEmpty ( ) {
        return n0.next==null;
    }

    public boolean isfull ( ) {
        if ( count == size  ) {
            return true;
        }
        return false;
    }

    class Node1{
        Node1 next=null;
        TT no;

        public Node1 ( TT no ) {
            this.no = no;
        }
    }


}

基于栈的计算器（可进行多位数运算）除法是整形取模，会存在误差。

public class Jisuanqi {
    String str="3+200*2-2";
    StackAsLinked<Integer> numStack = new StackAsLinked<> ();
    StackAsLinked<Character> proStack = new StackAsLinked<> ();
    public static void main ( String[] args ) {
        Jisuanqi j1 = new Jisuanqi ();
        j1.run ();
        }

  public boolean ispro(char c1){
      if(c1=='+'||c1=='-'||c1=='*'||c1=='/'){
          return true;
      }
      return false;
  }


    public int order ( char c1 ) {
        if ( c1 == '+' || c1 == '-' ) {
            return 1;
        } else if ( c1 == '*' || c1 == '/' ) {
            return 2;
        }
        return -1;
  }

  public void run() {
      //定义一个下标来取字符
      int index = 0;
      char pro;
      int num1;
      int num2;
      int sum = 0;
      int x=0;
      boolean bb=false;
      char c1;
      while ( true ) {
          //如果index位于最后一个了，就直接跳出循环了,遍历完成.
          if ( index == str.length ( ) ) {
              System.out.println ( "遍历完成" );
              break;
          }
          c1 = str.charAt ( index++ );
          //取出字符为空，继续取下一个
          if ( c1 == ' ' )
              continue;
          //如果字符为符号，准备存入符号栈中
          if ( ispro ( c1 ) ) {

              if(bb){
                  numStack.push (x);
                  bb=false;
              }
              //存入前判断符号栈是不是空的,是空的直接添加，不是空的就继续判断
              if ( proStack.count == 0 ) {
                  proStack.push ( c1 );
                  continue;
              }
              //判断运算次序，新加入的运算符顺序高于等于栈中第一个，直接加入
              if ( order ( c1 ) >= order ( proStack.back.no ) ) {
                  proStack.push ( c1 );
                  //运算符低于栈中第一个，先运算再加入
              } else {
                  //取出两个数字和运算符进行运算
                  num1 = numStack.pop ( );
                  num2 = numStack.pop ( );
                  pro = proStack.pop ( );
                  switch ( pro ) {
                      case '+':
                          sum = num1 + num2;
                          break;
                      case '-':
                          sum = num2 - num1;
                          break;
                      case '*':
                          sum = num2 * num1;
                          break;
                      case '/':
                          if ( num1 == 0 ) {
                              System.out.println ( "错误，除数不能为0" );
                              return;
                          }
                          sum = num2 / num1;
                          break;
                  }
                  //把计算结果放入栈，之后把运算符放进去
                  numStack.push ( sum );
                  proStack.push ( c1 );
              }

          }
          //如果字符不是符号，存入数字栈中
          else {
                //将数据暂存
              if ( ! bb ) {
                  x = Integer.valueOf ( c1 ) - 48;
                  bb = true;
              } else {
                  x = x * 10 + ( Integer.valueOf ( c1 ) - 48 );
              }

          }
      }
      if(bb){
          numStack.push (x);
          bb=false;
      }
      //现在遍历完成，将现有栈中的数据计算出结果就行了
      while ( true ) {
          if ( proStack.count!=0) {
              num1 = numStack.pop ( );
              num2 = numStack.pop ( );
              pro = proStack.pop ( );
              sum = jisuan ( num1 , num2 , pro );

              numStack.push ( sum );
          }else{
              System.out.println ("计算结果"+numStack.pop () );
              break;
          }
      }
  }

public int jisuan(int num01,int num02,char pro1){
    char pro=pro1;
    int num1=num01;
    int num2=num02;
    int sum=0;

    switch ( pro ){
        case'+':
            sum=num1+num2;
            break;
        case'-':
            sum=num2-num1;
            break;
        case'*':
            sum=num2*num1;
            break;
        case'/':
            if(num1==0){
               throw new RuntimeException ( "错误，除数不能为0" );
            }
            sum=num2/num1;
            break;
    }
    //把计算结果输出
    return sum;
}

}