1208: 計算整數四則運算表達式的結果
參考資料
資料結構（C語言版）嚴蔚敏 吳偉民 編著————表達式求值
題目
簡單四則運算。更多内容點選标題。
- 保證表達式合法。
- 運算符隻包含：加（+），減（-），乘（*），除（/）。
- 以等号（=）結束。
提示
- 表達式隻包含：數字字元，加，減，乘，除，等号這六種符号。
- 測試資料不存在分母為0的情況，代碼中不用考慮。
- 全部為int型，不存在浮點型，也就是說：3/2=1，5/2=2。
- 切記，雖然題目沒說多組輸入，但是測試資料有很多（我被被坑了）。
- 操作數可能不止一位，例如： 10+8= 。
測試資料（不像OJ的Simple Input跟沒有一樣QAQ）
輸入
-5/2+0+1*3+14=
520=
輸出
15
520
這兩組資料對了，你可以直接送出了，肯定對。
分析
這道題目很明顯是在考察棧的運用，不知道棧是什麼的，自己參考其他資料。這裡隻講題目思路。
有這本書的可以看看書（應該能看懂），沒有的話，我就稍微啰嗦一下。
四則運算規則不需要我說吧。下面是這道題目的運算關系表：
這裡要用到兩個
棧（Stack），分别是
運算數棧（opnd）和
運算符棧（optr）。分别儲存運算符和運算數。代碼聲明如下：
/**
1. @Field optr 運算符棧
*/
private Stack<Character> optr;
/**
2. @Field opnd 運算數棧
*/
private Stack<Integer> opnd;
算法思想：
- 表達式最後一個字元是 ’=’ ，是以将運算符棧棧底置為 ’=’ 。
- 依次讀取表達式中的每個字元，如果是數字字元，則将這個操作數進 opnd 棧，如果是運算符，則和 optr 棧頂運算符比較優先級後進行操作。
- 直到計算結束（ optr 棧頂和目前字元都為 ’=' 說明計算結束）。
測試資料 1 運算過程如下：
| 步驟 | optr（運算符棧） | opnd（運算數棧） | 剩餘字元 | 主要操作 |
|---|---|---|---|---|
| 1 | = | - 5/2+0+1*3+14= | opnd.push(0) | |
| 2 | = | - 5/2+0+1*3+14= | optr.push(’-’) | |
| 3 | = - | 5 /2+0+1*3+14= | opnd.push(5) | |
| 4 | = - | 0 5 | / 2+0+1*3+14= | optr.push(’/’) |
| 5 | = - / | 0 5 | 2 +0+1*3+14= | opnd.push(2) |
| 6 | = - / | 0 5 2 | + 0+1*3+14= | opnd.push(calculate(5,’/’,2)) |
| 7 | = - | 0 2 | + 0+1*3+14= | opnd.push(calculate(0,’-’,2)) |
| 8 | = | -2 | + 0+1*3+14= | optr.push(’+’) |
| 9 | = + | -2 | +1*3+14= | opnd.push(0) |
| 10 | = + | -2 0 | + 1*3+14= | opnd.push(calculate(-2,’+’,0)) |
| 11 | = | -2 | + 1*3+14= | optr.push(’+’) |
| 12 | = + | -2 | 1 *3+14= | opnd.push(1) |
| 13 | = + | -2 1 | * 3+14= | optr.push(’*’) |
| 14 | = + * | -2 1 | 3 +14= | opnd.push(3) |
| 15 | = + * | -2 1 3 | + 14= | opnd.push(calculate(1,’*’,3)) |
| 16 | = + | -2 3 | + 14= | opnd.push(calculate(-2,’+’,3)) |
| 17 | = | 1 | + 14= | optr.push(’+’) |
| 18 | = + | 1 | 1 4= | opnd.push(14) |
| 19 | = + | 1 14 | = | opnd.push(calculate(1,’+’,14)) |
| 20 | = | 15 | = | Output(opnd.peek()) |
【備注】手打不易，且看且珍惜。
【說明】1、左邊是
棧底，右邊是
棧頂。2、剩餘字元中的
加粗字元（也就是最左邊的字元）表示正在讀取的字元。3、
optr.push()表示進運算符棧；
opnd.push()表示進運算數棧；
calculate()表示二進制運算；
opnd.peek()表示擷取棧頂元素（Java的Stack類自帶方法）；
Output()表示輸出。4、第18步至19步沒看懂的閱讀代碼的
getInt()方法。
下圖為課本例題的過程圖：
代碼
/**
* time 268ms
* @author PengHao
* @version A2.0
* @date 2019-04-23 下午10:48:22
*/
import java.util.Scanner;
import java.util.Stack;
public class Main {
private Scanner sc;
/**
* @Field formal 算式
*/
private String formal;
/**
* @Field optr 運算符棧
*/
private Stack<Character> optr;
/**
* @Field opnd 運算數棧
*/
private Stack<Integer> opnd;
/**
* @Field index 正在讀取的式子中的字元的下标
*/
private int index;
public Main() {
sc = new Scanner(System.in);
char temp; // 臨時變量
while (sc.hasNext()) {
formal = sc.next(); // 式子
init(); // 初始化
temp = formal.charAt(index); // 擷取目前字元
// 隻有目前字元和運算符棧棧頂都是‘=’時，才退出循環，表示計算結束
while ('=' != temp || '=' != optr.peek()) {
if (Character.isDigit(temp)) { // 目前字元是數字
opnd.push(getInt()); // 将目前運算數入棧
} else { // 目前字元是運算符
if (0 == index) { // 這個字元是算式的第0個字元
opnd.push(0); // 将數字0入運算數棧棧頂
}
operate(); // 運算操作
}
temp = formal.charAt(index); // 擷取算式的目前的字元
}
System.out.println(opnd.peek()); // 輸出運算數棧棧頂（即算式結果）
}
sc.close();
}
/**
* Initializes the properties of the class
*/
private void init() {
optr = new Stack<Character>();
opnd = new Stack<Integer>();
optr.push('='); // 初始運算符棧有一個‘=’
index = 0; // 第0個字元
}
/**
* @return 式子中目前需要輸入的運算數
*/
private int getInt() {
int num = 0, n;
char temp;
do {
// char型轉成int型，并且下标向後移動一位
n = formal.charAt(index++) - '0';
num = num * 10 + n; // 轉成運算數
temp = formal.charAt(index); // 擷取目前字元
} while (Character.isDigit(temp)); // 目前字元是數字，則屬于同一個運算數
return num;
}
/**
* Arithmetic operations
*/
private void operate() {
int num1, num2; // 需要計算的兩個運算數
char op; // 需要計算的運算符
char a = optr.peek(); // 運算符棧的棧頂運算符
char b = formal.charAt(index); // 算式的目前的運算符
if ('>' == priority(a, b)) { // 棧裡面的運算符優先級較高
num2 = opnd.pop(); // 先出棧的是第二個運算數
op = optr.pop(); // 運算符
num1 = opnd.pop(); // 後出棧的是第一運算數
opnd.push(calculate(num1, op, num2)); // 運算結果入運算數棧
} else { // 目前運算符優先級較高
optr.push(b); // 目前運算符入運算符棧
index++; // 算式下标後移一位
}
}
/**
* @param a 第一個運算符
* @param b 第二個運算符
* @return > 如果 <b>a</b> 的優先級高于 <b>b</b> 的優先級</br>
* < 如果 <b>a</b> 的優先級低于 <b>b</b> 的優先級
*/
private char priority(char a, char b) {
if ('*' == a || '/' == a) { // a運算符優先級最高
return '>';
}
if ('*' == b || '/' == b) { // b運算符優先級最高
return '<';
}
if ('=' == a) { // a是‘=’，優先級肯定是最低的
return '<';
}
return '>'; // 從左到右運算順序，a優先級高于b（a在b左邊）
}
/**
* @param num1 第一個運算數
* @param op 兩個運算數之間的運算符
* @param num2 第二個運算數
* @return num1 op num2 的運算結果
*/
private int calculate(int num1, char op, int num2) {
switch (op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
default:
return 0;
}
}
public static void main(String[] args) {
new Main();
}
}
寫在最後：
- 如需轉載，請于首頁至少注明連結形式的wowpH的部落格這幾個字；
- 代碼原創，如需公開引用，不能删除首行注釋（作者，版本号，時間等資訊）。
- 如果有疑問歡迎評論留言，盡量解答。