中綴表達式: 表達式中操作符位于操作符中間
,如:(3+4)*5-6,上述通過棧實作的即中綴表達式電腦。
字首表達式():
波蘭表達式
,計算機在進行計算時
表達式中運算符在操作數前面
依次掃描,遇到操作數壓入操作數棧,遇到操作符彈出操作數棧棧頂的兩個元素進行元素,并将其結果壓入操作數棧繼續掃描。最終得到計算結果。
從右往左
如:(3+4)*5-6 =>
"- 6 * 5 + 4 3"
字尾表達式():
逆波蘭表達式,更适合計算機的運作
,計算機在進行計算時
表達式中運算符在操作數後面
依次掃描,遇到操作數壓入操作數棧,遇到操作符彈出操作數棧棧頂的兩個元素進行元素,并将其結果壓入操作數棧繼續掃描。最終得到計算結果。
從左往右
如:(3+4)*5-6 =>
"3 4 + 5 * 6 -"
中綴表達式基于棧的電腦實作:
package 棧;
import java.util.Stack;
/**
* @author lyq on 2019-12-24 9:53 上午
* @desc 棧實作表達式(隻含+、-、*、"\")電腦
* 實作思路:
* 建立兩個棧分别用于存放 操作數 和 操作符;
* 周遊表達式:
* - 如果周遊元素為數直接入操作數棧;
* - 如果周遊元素為操作符:
* - 如果目前操作符優先級小于等于操作數棧目前棧頂元素的優先級,則從操作數棧中彈出兩個操作數,并從符号棧彈出棧頂符号,根據彈出的操作符執行運算;
* 将結果入操作數棧;将目前操作符入操作數棧;
* - 如果目前操作符優先級大于操作數棧目前棧頂元素的優先級,則入操作數棧。
*/
public class StackCalculation {
private String expression = null;
public StackCalculation(String expression) {
this.expression = expression;
}
public void calculate(){
// 存放操作數的棧
Stack<Integer> numStack = new Stack();
// 存放操作符的棧
Stack<Character> operStack = new Stack<>();
char[] chars = expression.toCharArray();
// 用于處理
String tempMultiNum = "";
for (int i = 0;i < chars.length;i++) {
char c = chars[i];
if (!checkOperation(c)) {
tempMultiNum += c;
if (i == (chars.length-1)) {
numStack.push(Integer.parseInt(tempMultiNum));
}
continue;
} else {
if (tempMultiNum.length() > 0) {
numStack.push(Integer.parseInt(tempMultiNum));
tempMultiNum = "";
}
if (operStack.isEmpty()) {
operStack.push(c);
} else {
int cur = getPriority(c);
int top = getPriority(operStack.peek());
if (cur > top) {
operStack.push(c);
} else {
Integer numLater = numStack.pop();
Integer numBefore = numStack.pop();
Character topOper = operStack.pop();
int tempResult = cal(numBefore, numLater, topOper);
numStack.push(tempResult);
operStack.push(c);
}
}
}
}
while (!operStack.isEmpty()) {
Integer numLater = numStack.pop();
Integer numBefore = numStack.pop();
Character topOper = operStack.pop();
int tempResult = cal(numBefore, numLater, topOper);
numStack.push(tempResult);
}
System.out.println(numStack.pop());
}
/**
* 擷取操作符的優先級
* @param c
* @return
*/
private int getPriority(char c){
if (c == '*' || c == '/') {
return 1;
} else if (c == '+' || c == '-') {
return 0;
} else {
return -1;
}
}
/**
* 檢查周遊元素是否為操作符
* @param c
* @return
*/
private boolean checkOperation(char c) {
if (c == '+' || c == '-' || c == '*' || c == '/') {
return true;
}
return false;
}
/**
* 計算結果
* @param numBefore
* @param numLater
* @param oper
* @return
*/
private int cal(int numBefore, int numLater, char oper){
int tempResult = 0;
switch (oper) {
case '+':
tempResult = numLater + numBefore;
break;
case '-':
tempResult = numBefore - numLater;
break;
case '*':
tempResult = numBefore * numLater;
break;
case '/':
tempResult = numBefore/numLater;
break;
default:
break;
}
return tempResult;
}
public static void main(String[] args) {
StackCalculation stackCalculation = new StackCalculation("70*2+2-5*3-1");
stackCalculation.calculate();
}
}
中綴表達式轉字尾表達式
1、初始化兩個棧:運算符棧s1,存儲中間結果的棧s2;
2、從左至右掃描中綴表達式;
3、掃描到操作數時壓入s2;
4、掃描到運算符時:
(1)如果s1為空 或 s1棧頂為"(" 或 該運算符優先級高于s1棧頂運算符,則将該運算符入s1;
(2)否則将s1棧頂運算符壓入s2,繼續執行 4.(1) 的操作;
5、遇到括号時:
(1)如果是"(“直接壓入s1;
(2)如果是”)“則依次彈出s1棧頂運算符壓入s2,直到遇到”(",此時将這一對括号丢棄。
6、重複2-5,直到表達式最右邊;
7、将s1中的剩餘運算符依次彈出壓入s2;
8、依次彈出s2中的元素并輸出,
。
結果的逆序即為該中綴表達式的字尾表達式
package 棧;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author lyq on 2019-12-24 2:05 下午
* @desc 中綴表達式轉字尾表達式
*/
public class MidToSufferExp {
private String midExp;
public MidToSufferExp(String midExp) {
this.midExp = midExp;
}
/**
* 将中綴表達式轉換為list
* @return
*/
public static List<String> convertToList(String midExp){
List<String> result = new ArrayList<>();
int i = 0;
char c;
// 多位數
String multiNum;
do {
c = midExp.charAt(i);
// 如果c不是數字
if (c < 48 || c > 57) {
result.add(String.valueOf(c));
i++;
} else {
multiNum = "";
while (i < midExp.length() && (c = midExp.charAt(i)) >= 48 && (c = midExp.charAt(i)) <= 57) {
multiNum += midExp.charAt(i);
i++;
}
result.add(multiNum);
}
} while (i < midExp.length());
return result;
}
public static Stack convertToSuffuxExp(List<String> list) {
Stack<String> s1 = new Stack<>();
Stack<String> s2 = new Stack<>();
for (String s : list) {
// 如果是數字直接入s2
if (s.matches("\\d+")) {
s2.push(s);
// 如果是"(" 直接入s1
} else if (s1.size() == 0 || s.equals("(")){
s1.push(s);
// 如果是")",則執行括号消除操作
} else if (s.equals(")")) {
while (!(s1.peek().equals("("))){
s2.add(s1.pop());
}
// 消除括号
s1.pop();
} else {
// 擷取目前操作符的優先級
int cur = getPriority(s);
while ((!s1.isEmpty()) && (getPriority(s1.peek()) >= getPriority(s))) {
s2.push(s1.pop());
}
s1.push(s);
}
}
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2;
}
private static int getPriority(String s){
if (s.equals("*") || s.equals("/")) {
return 1;
} else if (s.equals("+") || s.equals("-")) {
return 0;
} else {
return -1;
}
}
public static void main(String[] args) {
String midExp = "3+(70*2)-6/2+3";
List<String> list = convertToList(midExp);
Stack stack = convertToSuffuxExp(list);
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}