Java用棧實現綜合計算器
棧
棧（stack）又名堆棧，它是一種運算受限的線性表 。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
概念隨便一看，反正就是先進后出的一種數據結構，什么是棧這里不做贅述，下面看一下如何在Java中，利用數組實現模擬一個棧。
Java實現棧
可以用數組來簡單的模擬出一個棧的結構。
棧一共兩個操作，入棧和出棧
我們只需要一個指針指向棧頂即可完成：
1.出棧的時候將棧頂指針指向的數據取出，指針左移一位指向新的棧頂數據
2.入棧的時候將棧頂指針后移一位，新的棧頂數據放入指針所在位置
注意：當然，由于數組存儲空間是定長的，需要指定棧的大小，出入棧也需要判斷棧空、棧滿
用類ArrayStack作為棧對象
1.屬性maxSize存放棧的大小，用于判斷棧是否滿
2.屬性stack[]是用于存放棧的數組
3.top指針指向棧頂，初始化指向-1（因為入棧要先后移）
4.方法有——查看棧頂數據、判斷棧是否空、判斷棧是否滿、入棧、出棧、打印棧
代碼如下：
class ArrayStack{
/**
* 棧的大小
*/
private int maxSize;
/**
* 數組，模擬棧
*/
private int[] stack;
/**
* top表示棧頂數據所在數組位置的下標,初始化為-1
*/
private int top = -1;
/**
* 構造器，初始化棧
* @param maxSize 棧的大小
*/
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
/**
* 返回當前棧頂的值，不出棧
* @return 當前棧頂的值
*/
public int topData(){
return stack[top];
}
/**
* 判斷棧是否滿
*/
public boolean isFull(){
return top==maxSize-1;
}
/**
* 判斷棧是否空
*/
public boolean isNull(){
return top==-1;
}
/**
* 入棧
* @param data 入棧的數據
*/
public void push(int data){
//先判斷棧是否是滿的
if (isFull()){
//如果是滿的，打印錯誤，直接返回
System.out.println("棧已滿");
return;
}
//棧沒滿，入棧
// top++;stack[top]=data;
stack[++top] = data;
}
/**
* 出棧
* @return 返回棧頂數據
*/
public int pop(){
//先判斷棧是否為空
if (isNull()){
//如果為空，拋出異常
throw new RuntimeException("棧為空，沒有可出棧數據");
}
//不為空執(zhí)行出棧
return stack[top--];
}
/**
* 顯示棧的情況，從棧頂顯示到棧底
*/
public void showStack(){
//先判斷是否為空棧
if (isNull()){
System.out.println("棧為空，沒有數據");
return;
}
//遍歷顯示棧
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}至此，一個簡單的棧結構就模擬完成了
那么?？梢杂脕碜鍪裁茨兀?/p>
進制轉換、判斷括號是否匹配、算數表達式的計算、中綴表達式轉換后綴表達式
本文來實現一個中綴表達式的計算、后綴表達式計算以及中綴表達式轉換后綴表達式
棧實現綜合計算器
首先分析，表達式由運算數和運算符組成，運算符具有優(yōu)先級問題，所以在計算一個表達式時，是根據運算符優(yōu)先級順序對運算數進行對應運算符的計算
那么首先需要一些工具方法對用于遍歷表達式時的判斷，和運算表達式時的計算
包括：
1.判斷字符是否是一個運算符
2.判斷字符是否是括號
3.判斷運算符的優(yōu)先級
4.根據運算符計算兩個數據
/**
* 判斷char字符是否是一個運算符
* @param operator 要檢測是否是運算符的char
* @return 是否為運算符
*/
static boolean isOperator(int operator){
return operator=='+'||operator=='-'||operator=='*'||operator=='/';
}
/**
* 判斷char字符是否是括號
*/
static boolean isBracket(int operator){
return operator=='('||operator==')';
}
/**
* 返回運算符優(yōu)先級（數字大優(yōu)先級高）
* @param operator 運算符
* @return 表示優(yōu)先級的int
*/
static int priority(int operator){
if (operator == '+' || operator == '-'){
return 0;
}
if (operator == '*' || operator == '/'){
return 1;
}
return -1;
}
/**
* 根據運算符計算兩個數據
* @param num1 數據1
* @param num2 數據2
* @param operator 運算符（+-*除）
* @return 運算結果
*/
static int calculate(int num1,int num2,int operator){
int res = 0;
switch (operator){
case '+':
res = num2 + num1;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num2 * num1;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}1.中綴表達式直接計算
這里實現直接計算一個中綴表達式，沒有寫入對括號的判斷，所以只能是計算最簡單的加減乘除
具體實現思路，需要兩個棧，一個棧放運算數，一個棧放運算符
遍歷整個算數表達式的字符串：
會有兩種情況，遇到運算符或者遇到運算數
1.如果遇到運算數就加入到數棧中
2.如果是運算符需要循環(huán)判斷符號棧的情況，如果符號棧不為空且當前運算符優(yōu)先級小于等于棧頂運算符，就彈出兩個運算數一個運算符進行計算，計算結果壓入數棧；直到符號棧為空或者當前運算符優(yōu)先級大于棧頂，就將當前運算符入符號棧
3.算術表達式遍歷結束后，繼續(xù)計算，循環(huán)彈出兩個數一個符號，計算結果入數棧，直到符號棧為空，此時數棧中剩下一個數字就是表達式的計算結果
/**
* 計算中綴表達式的結果（不能含有括號）
* @param expression 中綴表達式
* @return 結果
*/
static int calculateMid(String expression) {
//數字棧
ArrayStack numStack = new ArrayStack(10);
//運算符棧
ArrayStack operatorStack = new ArrayStack(10);
//遍歷字符串進行入棧等運算操作
for (int i = 0; i < expression.length(); i++) {
//遍歷到字符串中的一個字符
char ch = expression.charAt(i);
//判斷是否為運算符
if (isOperator(ch)) {
//如果是運算符,判斷當前符號棧是否為空
//不為空，判斷當前符號優(yōu)先級和棧中符號優(yōu)先級的關系進行操作
//當前運算符優(yōu)先級小于等于棧中運算符優(yōu)先級，從數棧中pop兩個數據，運算符棧中pop一個運算符進行計算，計算結果push進數棧，新運算符再次進行優(yōu)先級判斷
while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
int num1 = numStack.pop();
int num2 = numStack.pop();
int operator = operatorStack.pop();
int res = calculate(num1, num2, operator);
numStack.push(res);
}
//直到當前運算符優(yōu)先級大于棧中運算符優(yōu)先級或棧為空，再入棧
operatorStack.push(ch);
}else {
//如果不是運算符,判斷是否是數字
if (Character.isDigit(ch)) {
//如果是數字，準備記錄下這個數字
StringBuilder num = new StringBuilder(String.valueOf(ch));
//找到下一個字符判斷，進行拼接操作，直到下一個為運算符或沒有下一個字符為止
while (i+1 < expression.length()&&!isOperator(expression.charAt(i+1))) {
//如果還是數字，先將數字拼接,再i++
num.append(expression.charAt(i+1));
i++;
}
numStack.push(Integer.parseInt(num.toString()));
}else {
//如果不是數字（到這里就既不是數字也不是運算符）報錯表達式有誤
throw new RuntimeException("運算表達式有誤,不支持的符號:[ "+ch+" ]");
}
}
}
//遍歷結束后將棧中繼續(xù)計算直到數棧中只有一個數字，就是結果
while (!operatorStack.isNull()){
int num1 = numStack.pop();
int num2 = numStack.pop();
int operator = operatorStack.pop();
int res = calculate(num1, num2, operator);
numStack.push(res);
}
return numStack.pop();
}2.后綴表達式計算
后綴表達式是也稱逆波蘭表達式，是一種計算機更好處理的表達式結構
因為后綴表達式相當于按照優(yōu)先級、括號等，排好了計算順序，計算機只需要順序向后加載計算即可
用到一個數棧就夠了，只需要遍歷表達式，遇到數字直接入棧，遇到符號直接出棧兩個數字進行運算，將結果再入棧，直到表達式遍歷結束，棧中就剩下一個數字就是計算結果
代碼如下：
這里將表達式格式限制為每個不同元素用空格隔開，便不需要加載操作數時判斷多位數了
/**
* 計算后綴表達式
* @param expression 后綴表達式
* @return 計算結果
*/
static int calculateSuf(String expression){
//1.將后綴表達式拆開放入集合
String[] expressionList = expression.split(" ");
//2.創(chuàng)建數棧
ArrayStack numStack = new ArrayStack(10);
for (String s : expressionList) {
//判斷是否是符號
if (isOperator(s.charAt(0))) {
//是符號就出棧兩個數據進行計算
int num1 = numStack.pop();
int num2 = numStack.pop();
int res = calculate(num1, num2, s.charAt(0));
//計算結果入棧
numStack.push(res);
}else {
//不是符號轉換為數字入棧即可
int num;
try {
num = Integer.parseInt(s);
}catch (NumberFormatException e){
throw new RuntimeException("錯誤的表達式：[ "+s+" ]");
}
numStack.push(num);
}
}
return numStack.pop();
}中綴表達式轉后綴表達式
中綴表達式就是生活中使用的算數表達式
比如一個中綴表達式：1+((2+3)*4)-5
轉換為后綴表達式為：1 2 3 + 4 * + 5 -
目前，如果要我自己去轉換，一般采用樹來輔助，更好記憶和理解，將中綴表達式轉換成樹形結構，再后序遍歷這個樹就能得到后綴表達式
這個轉換過程，用算法來完成，是稍有些復雜的，轉換算法也是前人長時間的智慧結晶，沒有看到過轉換方法之前，自己想不到怎么轉換還算蠻正常的，重點體會一下這個思路就好，其實整個思路也是根據之前計算中綴表達式得來
轉換算法思路：
1.初始化兩個棧，一個是符號棧s1，一個是中間結果棧s2
2.從左到右掃描中綴表達式
3.遇到操作數直接入棧s2
4.遇到運算符還是循環(huán)判斷，當運算符棧不為空且當前運算符優(yōu)先級不大于棧頂運算符時，就彈出一個運算符壓入中間結果棧，直到棧為空或當前運算符優(yōu)先級大于棧頂運算符優(yōu)先級（這里判斷優(yōu)先級，會出現左括號，左括號當做最低優(yōu)先級，也就是遇到左括號就直接運算符入棧即可）
5.遇到括號時，如果是左括號，直接入棧s1；如果是右括號，依次彈出s1中的運算符壓入s2，直到遇見左括號為止，此時將一對括號丟棄
6.直到整個表達式遍歷結束，再將s1中剩余的運算符依次彈出壓入s2
此時s2棧彈出順序的逆序就是后綴表達式
代碼如下：
static String infixToSuffix(String infix){
//運算符棧
ArrayStack operatorStack = new ArrayStack(20);
//結果棧
ArrayStack resStack = new ArrayStack(20);
//遍歷掃描中綴表達式
for (int i = 0; i < infix.length(); i++) {
//遍歷到的一個字符
char ch = infix.charAt(i);
//判斷是否為運算符
if (isOperator(ch)){
//循環(huán)判斷如果運算符棧不為空且當前運算符優(yōu)先級不大于棧頂運算符
while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
//彈出運算符棧壓入結果棧
resStack.push(operatorStack.pop());
}
//當前運算符入運算符棧
operatorStack.push(ch);
}
//如果不是運算符再判斷是否是運算數，是就直接壓入結果棧
else if (Character.isDigit(ch)){
//如果是數字，記錄下這個數字壓入結果棧
StringBuilder num = new StringBuilder(String.valueOf(ch));
//找到下一個字符判斷，進行拼接操作，直到下一個為運算符或沒有下一個字符為止
while (i+1 < infix.length()&&Character.isDigit(infix.charAt(i+1))) {
//如果還是數字，先將數字拼接,再i++
num.append(infix.charAt(i+1));
i++;
}
resStack.push(Integer.parseInt(num.toString()));
}
//如果不是運算符也不是操作數，判斷是否為括號
else if (isBracket(ch)){
//如果是括號，判斷左括號壓入運算符棧
if (ch=='('){
operatorStack.push(ch);
}
//如果是右括號，依次彈出s1的運算符，壓入結果棧，直到遇見左括號（丟棄這一對括號）
else if (ch==')'){
while (true){
int top = operatorStack.pop();
if (top=='('){
break;
}
resStack.push(top);
}
}
}
}
//遍歷結束后，將運算符棧中剩余的運算符依次彈出壓入結果棧
while (!operatorStack.isNull()){
resStack.push(operatorStack.pop());
}
//遍歷結果棧返回后綴表達式字符串(這里是反的)
StringBuilder res = new StringBuilder();
while (!resStack.isNull()){
int pop = resStack.pop();
if (isOperator(pop)){
char popChar = (char) pop;
res.append(popChar).append(" ");
}else {
res.append(pop).append(" ");
}
}
//將結果字符串反轉返回后綴表達式
String s = res.toString();
String[] s1 = s.split(" ");
StringBuilder builder = new StringBuilder();
for (int i = s1.length-1; i >= 0; i--) {
builder.append(s1[i]).append(" ");
}
return builder.toString();
}思考：
最后出棧順序的倒敘才是后綴表達式，那么是否可以用隊列來代替s2棧呢？
是完全可以的，s2在整個過程只有入棧操作，更換為隊列進行入隊，最終棧先進后出是逆序，隊列先進先出就是順序的。
到此這篇關于Java用棧實現綜合計算器的文章就介紹到這了,更多相關Java綜合計算器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
一文學會如何在SpringBoot中使用線程池執(zhí)行定時任務
在開發(fā)現代應用程序時，定時任務是一項常見的需求，SpringBoot提供了一個強大的定時任務框架，可以輕松地執(zhí)行各種定時任務，結合線程池的使用，可以更好地管理任務的執(zhí)行，提高系統(tǒng)的性能和穩(wěn)定性，本文將介紹如何在Spring Boot中使用線程池執(zhí)行定時任務2023-06-06
使用Spring Expression Language (SpEL)全面解析表達式
這篇文章主要介紹了使用Spring Expression Language (SpEL)全面解析表達式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
Apache Commons fileUpload文件上傳多個示例分享
這篇文章主要為大家分享了Apache Commons fileUpload文件上傳4個示例,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10
springboot整合Dubbo與Feign的實現?(無注冊中心)
本文主要介紹了springboot整合Dubbo與Feign的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-04-04
這篇文章主要介紹了Java?awt-對話框簡單實現方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
這篇文章主要介紹了spring注解@Service注解的使用解析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
緩存，在我們日常開發(fā)中是必不可少的一種解決性能問題的方法。簡單的說，cache?就是為了提升系統(tǒng)性能而開辟的一塊內存空間。本文將為大家介紹一個Java本地緩存的工具——LoadingCache，感興趣的可以了解一下2021-12-12
在本篇文章里小編給大家整理了一篇關于java Iterator.remove()實例方法分析，有興趣的朋友們跟著學習下。2021-01-01
JavaWeb JDBC + MySql 通訊錄實現簡單的增刪改查功能案例詳解
這篇文章主要介紹了JavaWeb JDBC + MySql 通訊錄實現簡單的增刪改查功能,結合具體案例形式詳細分析了JavaWeb JDBC + MySql數據庫連接、增刪改查等相關操作技巧與注意事項,需要的朋友可以參考下2019-08-08
這篇文章主要介紹了為什么不推薦使用BeanUtils屬性轉換工具，本文通過示例代碼給大家詳細介紹，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-07-07