將中綴表達式轉為后綴表達式的步驟如下:
- 創建一個空棧和一個空列表,用于存儲操作符和后綴表達式。
- 從左到右掃描中綴表達式的每個元素。
- 如果當前元素是操作數(數字),將其直接添加到后綴表達式列表中。
- 如果當前元素是操作符,進行如下處理:
- 如果棧為空,或者當前操作符是左括號"(",直接將操作符入棧。
- 如果當前操作符是右括號")",則從棧中依次彈出操作符,直到遇到左括號為止,并將這些操作符依次添加到后綴表達式列表中。
- 如果當前操作符優先級低于棧頂操作符,將棧頂操作符彈出并添加到后綴表達式列表中,重復該步驟直到當前操作符優先級高于棧頂操作符或棧為空,然后將當前操作符入棧。
- 如果當前操作符優先級高于棧頂操作符,直接將當前操作符入棧。
- 掃描完整個中綴表達式后,將棧中剩余的操作符依次彈出并添加到后綴表達式列表中。
- 后綴表達式列表即為轉換后的后綴表達式。
例如,將中綴表達式"3 + 4 * 2 / (1 - 5)"轉換為后綴表達式的過程如下:
中綴表達式:3 + 4 * 2 / (1 - 5)
后綴表達式:3 4 2 * 1 5 - / +
具體操作步驟:
- 3直接加入后綴表達式列表中。
- +為操作符,直接入棧。
- 4直接加入后綴表達式列表中。
- *優先級高于+,直接入棧。
- 2直接加入后綴表達式列表中。
- /優先級高于*,直接入棧。
- (入棧。
- 1直接加入后綴表達式列表中。
- -為操作符,優先級低于(,直接入棧。
- 5直接加入后綴表達式列表中。
- )遇到),彈出棧中操作符直到遇到(,將彈出的操作符加入后綴表達式列表中。
- 掃描結束后,將棧中剩余的操作符依次彈出并加入后綴表達式列表中。
最終得到后綴表達式:3 4 2 * 1 5 - / +