藍橋杯-棧的應用-表達式的計算

問題描述

　　輸入一個隻包含加減乖除和括号的合法表達式，求表達式的值。其中除表示整除。

輸入格式

　　輸入一行，包含一個表達式。

輸出格式

　　輸出這個表達式的值。

樣例輸入

1-2+3*(4-5)

樣例輸出

-4

資料規模和約定

　　表達式長度不超過100，表達式運算合法且運算過程都在int内進行。

這道題需要用到資料結構中棧的應用，利用棧的先進後出原理，先把中綴表達式轉換成字尾表達式，然後進行計算；例如：
           

++*+  // 中綴表達式，意思是說運算符号在兩個數的中間
    #2#+#5#*+#+ // 字尾表達式。符号在兩個運算數後面，# 是為了區分數。
           

轉換為字尾表達式的過程為：

1. 先定義兩個棧s1 和s2。s1表示用來存儲數字，s2 用來存儲符号。
2. 周遊表達式中的字元。
3. 如果為數字，則直接入s1棧，如果目前下一個字元為符号的話需要在數字後面加上’#’，來區分數字；
4. 如果為字元，當為’(’ 或 目前運算符的權值大于s2棧頂的符号元素的權值時可以直接入 s2 棧。
5. 當遇到 ‘)’ 時，将s2 的棧頂元素依次出棧，然後依次儲存到s1 中，知道遇到 ‘(’ 時，‘（’出棧後停止出棧，‘（’不儲存到 s1 中。‘）’也不儲存到s2 中。就等于消去括号。
6. 當權值小于棧頂元素時，也是s2 的元素依次出棧，知道目前元素大于棧頂元素後停止出棧，然後目前元素入s2 棧。
7. 重複步驟 3~6，知道周遊完所有元素。
8. 将s2 中的所有元素依次出棧到 s1 棧中。轉換完畢。

得到運算結果的過程

1. 颠倒s1 中的元素位置，s1依次出棧到s2 中。此時s1 為空，s2為後最表達式，下面将用s1儲存運算的數，s2 為表達式，聲明一個文本型變量num，用來拼接數字（用法見步驟3）。
2. 将s2中的元素依次出棧。
3. 如果是數字，并且s2棧頂元素是‘#’，那麼将元素轉換字元添加到num中，然後成後入s1棧并清空num用于下一個數字。如果還是數字，則用num加上目前數組繼續下一次周遊。
4. 如果遇到運算符号，則将s1 中從棧頂出棧兩個元素，然後根據符号進行相應的運算(需要注意的是棧頂元素是第二個運算數，例如從棧頂依次出棧的數字為x , y, 在進行除運算時，需要y/x)，然後将結果入s1 棧
5. 重複上述步驟，直到s2 為空時，運算結束。

下面獻上渣渣代碼：

import java.util.Scanner;
import java.util.Stack;
public class Main {
    //進行運算
    public static int yunSuan(char f,int x, int y){
        switch(f){
        case '-':
            return x-y;         
        case '+': 
            return x+y;
        case '*':
            return x*y;
        case '/':
            if(y == ) {
                new ArithmeticException().printStackTrace();
                System.exit();
            }else{
                return x/y;
            }
        default :
            return ;
        }
    }

    /**
     * 判斷是否為數字
     * 
     * @param n
     * @return
     */
    public static boolean judgeNum(char n) {
        if (n >= '0' && n <= '9')
            return true;
        return false;
    }

    /**
     * 傳回各個符号的權值
     * 
     * @param c
     * @return
     */

    public static int quanZhi(char c) {
        int quan = ;
        if (c == '+' || c == '-')
            quan = ;
        else if (c == '*' || c == '/')
            quan = ;
        else if(c == '(')
            quan = ;
        return quan;
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        char[] biaodashi = scan.next().toCharArray();
        scan.close();
        Stack s1 = new Stack(); // 存儲數字 48~57
        Stack s2 = new Stack(); // 存儲符号

        for (int i = ; i < biaodashi.length; i++) {
            // 判斷是符号還是數字
            if (judgeNum(biaodashi[i])) {
                s1.push(biaodashi[i]);
//              System.out.println(biaodashi[i]);
                if (i == biaodashi.length -  || (!judgeNum(biaodashi[i + ])))
                    s1.push('#');
            } else {
                if (s2.empty() || biaodashi[i] == '(' || quanZhi(biaodashi[i]) > quanZhi((char) s2.peek())) {
                    s2.push(biaodashi[i]);
//                  System.out.println(11111111);
                }else if(biaodashi[i] == ')'){
                    while (!s2.empty()) {
                        char c = (char)s2.pop();
                        if(c == '(')
                            break;
                        else{
                            s1.push(c);
//                          System.out.println(c+" 2 s1 push");
                        }
                    }
                }else if(quanZhi(biaodashi[i]) <= quanZhi((char) s2.peek())){
                    while (!s2.empty()) {
                        char c = (char)s2.peek();
                        if(quanZhi(biaodashi[i]) > quanZhi(c) || c == '('){
                            break;
                        }else{
                            s1.push((char)s2.pop());
                        }
//                      System.out.println(c+" 3 s1 push");
                    }
                    s2.push(biaodashi[i]);
                }
            }

        }
        // 将s2 中的 所有元素添加到s1 末尾
        while (!s2.empty()) {
            s1.push((char)s2.pop());
        }
        // 颠倒s1 的順序   儲存到s2 中
        while (!s1.empty()) {
            s2.push((char)s1.pop());
        }
//      String s1Str = "", s2Str="";
//      System.out.println("s1");
//      while (!s1.empty()) {
            s1Str = s1.pop() + s1Str;
//          System.out.print(s1.pop());
            s1Str += s1.pop();
//      }
//      System.out.println(s1Str);
//      System.out.println("s2");
//      while (!s2.empty()) {
            s2Str = s2.pop() + s2Str;
//          System.out.print(s2.pop());
//      }
//      System.out.println(s2Str);      


        int result = ; 
        String num = "";
        while(!s2.empty()){
            char c = (char) s2.pop();
            if(judgeNum(c)){
                num += String.valueOf(c);
                continue;
            }

            if(c == '#') {
                s1.push(Integer.parseInt(num));
//              System.out.println("s1 push "+num);
                num = "";
            }else{
                int y =(int) s1.pop();
                int x =(int) s1.pop();
                result = yunSuan(c, x, y);
                s1.push(new Integer(yunSuan(c, x, y)));
//              System.out.println("s1 push "+result);
            }
        }
        System.out.println(result);
    }
}