数据结构--栈的应用（括号匹配、表达式求值（中缀转后缀））

我就是我 2021-08-13 22:20 533阅读 0赞

### 栈的应用 ###

1.  栈是嵌套调用机制的实现基础
2.  使用栈以非递归方式实现递归算法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

### 判断表达式中圆括号是否匹配 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]

package pers.zhang.stack;
    
    /** * @author zhang * @date 2020/1/16 - 14:42 * * 栈应用：括号匹配 */
    public class Exp_bracket { 
        //判断expstr表达式中的圆括号是否匹配，若匹配，返回空串，否则返回错误信息
        public static String isValid(String expstr){ 
            SeqStack<String> stack = new SeqStack<String>(expstr.length());  //顺序栈
    
            for (int i = 0; i < expstr.length(); i++){ 
                char ch = expstr.charAt(i);
                switch(ch){ 
                    case '(':
                        stack.push(ch + "");//左括号入栈
                        break;
                    case ')':
                        if (stack.isEmpty() || !stack.pop().equals("("))  //遇见右括号时，出栈
                            return "期望(";//判断出栈字符是否为左括号
                }
            }
            return (stack.isEmpty()) ? "" : "期望)";           //返回空串表示没有错误
        }
    
        public static void main(String args[])
        { 
            String expstr = "((1+2)*3+4)";
            System.out.println(expstr + " " + isValid(expstr));
        }
    }
    
    /* 程序多次运行时，若expstr分别表示不同的表达式字符串，运行结果如下： ((1+2)*3+4) ((1+2)*3+4 期望) ((1+2)*3+4))( 期望( */

### 使用栈计算表达式值 ###

![在这里插入图片描述][20200116145113199.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]  
1.将中缀表达式转换为后缀表达式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]  
2.后缀表达式求值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]\`\`\`java  
package pers.zhang.stack;

/\*\*

*  @author zhang
 *  @date 2020/1/16 - 14:52
 *  
 *  栈应用：表达式求值  
    \*/  
    public class Expression \{
    
    //返回expstr的后缀表达式  
    public static String toPostfix(String expstr)\{  
    SeqStack stack = new SeqStack(expstr.length()); //创建运算符栈，顺序栈  
    String postfix = “”;//记载后缀表达式  
    int i = 0;  
    while (i < expstr.length())  
    \{  
    char ch = expstr.charAt(i);  
    switch (ch)\{  
    case ‘+’: //遇到＋、－运算符，与栈顶元素比较  
    case ‘-’:  
    while (!stack.isEmpty() && !stack.get().equals("("))  
    postfix += stack.pop();  
    stack.push(ch + “”); //当前运算符入栈  
    i++;  
    break;  
    case '*’: //遇到*、/ 运算符  
    case ‘/’:  
    while (!stack.isEmpty() && (stack.get().equals("\*") || stack.get().equals("/")))  
    postfix += stack.pop();  
    stack.push(ch+"");  
    i++;  
    break;  
    case ‘(’:  
    stack.push(ch + “”); //遇到左括号，入栈  
    i++;  
    break;  
    case ‘)’:  
    String out = stack.pop(); //遇到右括号，出栈，若栈空返回null  
    while (out!=null && !out.equals("("))\{ //判断出栈字符是否为左括号  
    postfix += out;  
    out = stack.pop();  
    \}  
    i++; break;  
    default:  
    while (i<expstr.length() && ch>=‘0’ && ch<=‘9’)\{ //遇到数字时，加入到后缀表达式  
    postfix += ch;  
    i++;  
    if (i < expstr.length())  
    ch = expstr.charAt(i);  
    \}  
    postfix += " "; //添加空格作为数值之间的分隔符  
    \}  
    \}  
    while (!stack.isEmpty())  
    postfix += stack.pop();  
    return postfix;  
    \}
    
    //计算后缀表达式的值  
    public static int value(String postfix)\{  
    LinkedStack stack = new LinkedStack(); //创建操作数栈，链式栈  
    int i = 0, result = 0;  
    while (i < postfix.length())\{ //逐个检查后缀表达式中的字符  
    char ch = postfix.charAt(i);  
    if (ch >= ‘0’ && ch <= ‘9’)\{ //遇到数字字符  
    result = 0;  
    while (ch != ’ ')\{ //字符串转化为数值  
    result = result \* 10 + Integer.parseInt(ch + “”);  
    i++;  
    ch = postfix.charAt(i);  
    \}  
    i++;  
    stack.push(new Integer(result)); //操作数入栈  
    \}else\{  
    int y = stack.pop().intValue(); //出栈两个操作数  
    int x = stack.pop().intValue();  
    switch (ch)\{ //根据运算符分别计算  
    case ‘+’:  
    result = x + y;  
    break;  
    case ‘-’:  
    result = x - y;  
    break;  
    case ‘\*’:  
    result = x \* y;  
    break;  
    case ‘/’:  
    result = x / y;  
    break; //整除，除数为0时将抛出异常  
    \}  
    stack.push(new Integer(result)); //运算结果入栈  
    i++;  
    \}  
    \}  
    return stack.pop().intValue(); //返回运算结果  
    \}
    
    public static void main(String args\[\])\{  
    String expstr="121+10\*(53-49+20)/((35-25)*2+10)+11";  
    String postfix = toPostfix(expstr);  
    System.out.println("expstr= " + expstr);  
    System.out.println("postfix= " + postfix);  
    System.out.println("value= " + value(postfix));  
    \}  
    \}  
    /*  
    程序运行结果如下：  
    expstr= 121+10\*(53-49+20)/((35-25)\*2+10)+11  
    postfix= 121 10 53 49 -20 +\*35 25 -2 \*10 +/+11 +  
    value= 140

expstr= 121+10\*(53-49+20)/((35-25)\*2+10)+11/0  
postfix= 121 10 53 49 -20 +\*35 25 -2 \*10 +/+11 0 /+  
Exception in thread “main” java.lang.ArithmeticException: / by zero  
at Expression.value(Expression.java:79)  
at Expression.main(Expression.java:93)

\*/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/b00f3e71aa8c4036a9080c91a367bbee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/1f1b278c726c47de9fd1111d92a8db62.png
[20200116145113199.png]: /images/20210813/0f3df75e088a405dac65abfe4722da78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/b8c76d7e1d9d4852a6122edc24084996.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/4700f1cb3ebe4068b6b43b9f25cec33c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]: /images/20210813/bdeac60dec1a47db8a744a824d81fa67.png