数据结构-02 图解中缀表达式转后缀表达式并计算值

目录:

1.图解中缀表达式转后缀表达式

通过 数据结构-01-图解后缀表达式值计算方式 我们了解到后缀表达式(例如:9 3 1 – 3 * + 10 2 /+)对计算机运算的方便,但是它却让我们这些人类十分的难受,因此我们需要在设计一个,中缀表达式转后缀表达式的程序来一劳永逸.

规则:依次遍历表达式,
1.如果是数字就添加到后缀表达式上(相反于数据结构-01-图解后缀表达式值计算方式
2.如果是符号就更栈顶Top符号比较优先级,低的输入会导致出栈(就是栈中高于或者等于都会全部出栈到后缀表达式上)
(符号的优先顺序为,乘除 > 加减 > 括号(括号的情况比较特殊,请结合代码和图解详细分析))

这里是一个 中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式 “9 3 1 – 3 * + 10 2 /+”的例子(我们使用空格将元素分开)

new 一个空栈
1.第一个是数字9,1.数字就添加到后缀表达式上
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
2.第二个是+,判断栈顶的,只有低的输入才会导致出栈,因此这里将+加号入栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
3.第三个是左括号 ( ,这里比较特殊,因为是左括号直接入栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
4.第四个是数字3,.数字就添加到后缀表达式上
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
5.第五个是减号, 我们需要判断栈顶的符号,左括号的优先级是最小的,这里直接将减号入栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
6.第六个是1,.数字就添加到后缀表达式上
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
7.第七-个是右括号,括号是优先级最低的,特殊我们直接找到左括号,将括号中的东西减号(-)出栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
8.第八个是乘法,判断符号优先级高于加法,因为只有低级输入才会导致出栈,这里直接入栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
9.第九个是 3,数字直接输出到后缀表达式中
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
10.第十个是 +,低级输入会导致出栈(这里的+号的等级小于 * 等于 + ,所以栈中的 * 和 +好都会出栈,然后第十个加号入栈)
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
11.第十一个是 10,数字直接全部输出到后缀表达式(大家请这里思考一个问题:像10这样的2位数或者多位数我们如何遍历得到的是一个元素 10,而不是2个元素 1,0 呢?(后面的代码将会实现这个功能))
《数据结构-02 图解中缀表达式转后缀表达式并计算值》

12.第十二个是除 / ,符号比较优先级 ,除法的优先级高于加法,只有低输入才会导致出栈,-所以这里直接入栈
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
13.第十三 是 2,数字直接输出到后缀表达式中,循环结束
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
14.循环结束后将栈中所有的元素依次出栈,-添加到后缀表达式后面。程序结束
《数据结构-02 图解中缀表达式转后缀表达式并计算值》

2.代码

如果你不能很好的理解这个代码,建议画出
1.后缀表达式的计算方法-图解
2.图解中缀表达式转后缀表达式

java

/** * @author 嘉文 */
public class InfixToPostfix { 
    public String infixToPostfix(String infix) { 
        //init stack
        MyStack myStack = new MyStack(infix.length());
        //postfix.
        StringBuilder postfix = new StringBuilder();
        int length = infix.length();
        for (int i = 0; i < length; i++) { 
            char tempChar;
            char charAt = infix.charAt(i);
            switch (charAt) { 
                //左括号直接入栈,不用过多解释
                case '(':
                    myStack.push(charAt);
                    break;
                //如果遇到 +-,低级会导致一次出栈.
                case '+':
                case '-':
                    //出栈
                    while (!myStack.isEmpty()) { 
                        tempChar = myStack.pop();
                        if (tempChar == '(') { 
                            myStack.push(tempChar);
                            break;
                        }
                        postfix.append(" ").append(tempChar);
                    }
                    myStack.push(charAt);
                    break;
                case '*':
                case '/':
                    while (!myStack.isEmpty()){ 
                        tempChar = myStack.pop();
                        if (tempChar == '('||tempChar == '+' ||tempChar == '-') { 
                            myStack.push(tempChar);
                            break;
                        }
                        postfix.append(" ").append(tempChar);
                    }
                    myStack.push(charAt);
                    break;
                case ')':
                    while (!myStack.isEmpty()){ 
                        tempChar = myStack.pop();
                        if (tempChar != '('){ 
                            postfix.append(" ").append(tempChar);
                        }else { 
                            break;
                        }
                    }
                    break;
                default:
                    postfix.append(" ").append(charAt);
                    //if length enough
                    if (i<length-1){ 
                        int j = i + 1;
                        char nextNumber = infix.charAt(j);
                        while ((nextNumber+"").matches("^[0-9]*")&&j<length){ 
                            postfix.append(nextNumber);
                            nextNumber = infix.charAt(++j);
                        }
                        i = j-1;
                    }
                    break;


            }
        }
        while (!myStack.isEmpty()) { 
            postfix.append(" ").append(myStack.pop());
        }
        return postfix.toString().trim();
    }
    public int getValueOfInfix(String infix){ 
        String postfix = infixToPostfix(infix);
        String[] items = postfix.split(" ");
        MyStack myStack = new MyStack(items.length);
        int length = items.length;
        for (int i = 0; i < length; i++) { 
            String tempItem = items[i];
            switch (tempItem){ 
                case "+":
                    char first = myStack.pop();
                    char second = myStack.pop();
                    int result = (int)second + (int)first;
                    myStack.push((char)result);
                    break;
                case "-":
                    char first2 = myStack.pop();
                    char second2 = myStack.pop();
                    int result2 = (int)second2 - (int)first2;
                    myStack.push((char)result2);
                    break;
                case "*":
                    char first3 = myStack.pop();
                    char second3 = myStack.pop();
                    int result3 = (int)second3 * (int)first3;
                    myStack.push((char)result3);
                    break;
                case "/":
                    char first4 = myStack.pop();
                    char second4 = myStack.pop();
                    int result4 = (int)second4 / (int)first4;
                    myStack.push((char)result4);
                    break;
                //if is number.
                default:
                    int charInt = Integer.parseInt(tempItem);
                    myStack.push((char)charInt);
                    break;
            }
        }
        return myStack.pop();
    }

    /** * 这是一个简单的栈实现 */
    class MyStack { 
        private char[] stackArray;
        private int topIndex ;

        public MyStack(int maxSize) { 
            stackArray = new char[maxSize];
            topIndex = -1;
        }
        public void push(char newTopItem){ 
            stackArray[++topIndex] = newTopItem;
        }
        public char pop(){ 
            return stackArray[topIndex--];
        }
        public char peek(){ 
            return stackArray[topIndex];
        }
        public boolean isEmpty(){ 
            return topIndex<0;
        }
    }
}

测试


    public static void main(String[] args) { 
        int valueOfInfix = new InfixToPostfix().getValueOfInfix("9+(3-1)*3+10/2");
        System.out.println(valueOfInfix);
    }

输出:
《数据结构-02 图解中缀表达式转后缀表达式并计算值》
计算正确

    原文作者:邓嘉文Jarvan
    原文地址: https://blog.csdn.net/jarvan5/article/details/109207355
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞