問題描述
輸入一個隻包含加減乖除和括号的合法表達式,求表達式的值。其中除表示整除。
輸入格式
輸入一行,包含一個表達式。
輸出格式
輸出這個表達式的值。
樣例輸入
1-2+3*(4-5)
樣例輸出
-4
資料規模和約定
表達式長度不超過100,表達式運算合法且運算過程都在int内進行。
這道題需要用到資料結構中棧的應用,利用棧的先進後出原理,先把中綴表達式轉換成字尾表達式,然後進行計算;例如:
++*+ // 中綴表達式,意思是說運算符号在兩個數的中間
#2#+#5#*+#+ // 字尾表達式。符号在兩個運算數後面,# 是為了區分數。
轉換為字尾表達式的過程為:
- 先定義兩個棧s1 和s2。s1表示用來存儲數字,s2 用來存儲符号。
- 周遊表達式中的字元。
- 如果為數字,則直接入s1棧,如果目前下一個字元為符号的話需要在數字後面加上’#’,來區分數字;
- 如果為字元,當為’(’ 或 目前運算符的權值大于s2棧頂的符号元素的權值時可以直接入 s2 棧。
- 當遇到 ‘)’ 時,将s2 的棧頂元素依次出棧,然後依次儲存到s1 中,知道遇到 ‘(’ 時,‘(’出棧後停止出棧,‘(’不儲存到 s1 中。‘)’也不儲存到s2 中。就等于消去括号。
- 當權值小于棧頂元素時,也是s2 的元素依次出棧,知道目前元素大于棧頂元素後停止出棧,然後目前元素入s2 棧。
- 重複步驟 3~6,知道周遊完所有元素。
- 将s2 中的所有元素依次出棧到 s1 棧中。轉換完畢。
得到運算結果的過程
- 颠倒s1 中的元素位置,s1依次出棧到s2 中。此時s1 為空,s2為後最表達式,下面将用s1儲存運算的數,s2 為表達式,聲明一個文本型變量num,用來拼接數字(用法見步驟3)。
- 将s2中的元素依次出棧。
- 如果是數字,并且s2棧頂元素是‘#’,那麼将元素轉換字元添加到num中,然後成後入s1棧并清空num用于下一個數字。如果還是數字,則用num加上目前數組繼續下一次周遊。
- 如果遇到運算符号,則将s1 中從棧頂出棧兩個元素,然後根據符号進行相應的運算(需要注意的是棧頂元素是第二個運算數,例如從棧頂依次出棧的數字為x , y, 在進行除運算時,需要y/x),然後将結果入s1 棧
- 重複上述步驟,直到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);
}
}