天天看點

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

問題描述

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

輸入格式

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

輸出格式

  輸出這個表達式的值。

樣例輸入

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

繼續閱讀