数据结构-栈

迷南。 2022-12-28 11:21 8阅读 0赞

# 栈 #

## 定义 ##

限制插入和删除只能在表的末端进行操作，也就是栈顶进行操作。符合先进后出的特点。Java中栈的实现是 通过数组。

例如：把1,2,3,4插入栈中，则存储结构如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]  
栈的简单应用-计算器

代码如下:

import java.util.Stack;
    
    /**
     * 实现带括号的四则运算
     */
    public class CalculatorUtil {
    
        public static void main(String[] args) {
            System.out.println(CalculatorUtil.Calculator("1+2*3.0+(1+1*3)+5"));
        }
    
        public static double Calculator(String expression){
            char[] chars = expression.toCharArray();
            //存储计算结果
            Stack<Double> result=new Stack<>();
            //存储操作
            Stack<Character> oper=new Stack<>();
            //临时存储数值
            StringBuilder num=new StringBuilder();
            for(int i=0;i<chars.length;i++){
                if(chars[i]=='+' || chars[i]=='-'  || chars[i]=='*' || chars[i]=='/' ){
                    //数值存入结果栈，并先进行乘除操作
                    if(!oper.isEmpty() && (oper.peek()=='*' || oper.peek()=='/')){
                            dealSum(oper.pop(),result,result.pop(),Double.parseDouble(num.toString()));
                    }else {
                        result.push(Double.parseDouble(num.toString()));
                    }
                    //清空临时数值
                    num.setLength(0);
                    oper.push(chars[i]);
                }else if(chars[i]=='('){
                    //存储左括号
                    oper.push(chars[i]);
                }else if(chars[i]==')'){
                    char operLast;
                    //一致进行出栈操作直到遇到左括号
                    while ((operLast=oper.pop())!='('){
                        dealSum(operLast,result,result.pop(),result.pop());
                    }
                }else {
                    //拼接数值
                    num.append(chars[i]);
                }
            }
            if(num.length()>0){
                result.push(Double.parseDouble(num.toString()));
            }
            //将剩余的操作出栈
            while (!oper.isEmpty()){
                dealSum(oper.pop(),result,result.pop(),result.pop());
            }
            return result.peek();
        }
    
        private static void dealSum(char oper,Stack<Double> result,double numFirst,double numSecond){
            switch (oper){
                case '+':
                    result.push(numFirst+numSecond);
                    break;
                case '-':
                    result.push(numFirst-numSecond);
                    break;
                case '*':
                    result.push(numFirst*numSecond);
                    break;
                case '/':
                    result.push(numFirst/numSecond);
                    break;
            }
        }
    
    }

例如: 1+2.0\*3+(1+1\*3)+5

把输入的字符串转为字符数组，我们通过两个栈进行操作，result存储计算结果，operate存储操作。

第1轮操作

result: \[1\]

operate:\[\]

第2轮操作

result: \[1\]

operate:\[+\]

第3轮操作

result: \[1,2.0\]

operate:\[+\]

第4轮操作

result: \[1,2.0\]

operate:\[+,\*\]

第5轮操作

result: \[1,6.0\]

operate:\[+\]

第6轮操作

result: \[1,6.0\]

operate:\[+,+\]

第7轮操作

result: \[1,6.0\]

operate:\[+,+,(\]

第8轮操作

result: \[1,6.0,1\]

operate:\[+,+,(,+\]

第9轮操作

result: \[1,6.0,1,1\]

operate:\[+,+,(,+\]

第10轮操作

result: \[1,6.0,1,1\]

operate:\[+,+,(,+,\*\]

第11轮操作

result: \[1,6.0,1,1,3\]

operate:\[+,+,(,+,\*\]

第12轮操作

result: \[1,6.0,4\]

operate:\[+,+\]

第13轮操作

result: \[1,6.0,4\]

operate:\[+,+,+\]

第14轮操作

result: \[1,6.0,4,5\]

operate:\[+,+,+\]

第15轮操作

result: \[1,6.0,9\]

operate:\[+,+\]

第16轮操作

result: \[1,15.0\]

operate:\[+\]

第17轮操作

result: \[16.0\]

operate:\[\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/f1a1423709854fda81a6a37439c65704.png