数据结构—栈的应用举例【算术表达式求值转换、后缀表达式求值计算】

package data.linear_table.stack_queue;
import data.linear_table.node.Node;
//链栈类
public class LinkStack implements IStack {
    private Node top ;      //栈顶元素的引用
    //将栈置空
    @Override
    public void clear() {
        top = null ;
    }
    //判断链栈是否为空
    @Override
    public boolean isEmpty() {
        return top == null ;
    }
    //求链栈的长度
    @Override
    public int length() {
        Node p = top ;      //初始化,p指向栈顶元素
        int length = 0 ;    //length为计数器
        //从栈顶元素开始向后查找，直到p为空
        while (p != null ) {
            p = p.next ;    //p指向后继结点
            length++ ;      //长度增加1
        }
        return length ;
    }
    //取栈顶元素并返回其值
    @Override
    public Object peek() {
        //栈如果不为空
        if (!isEmpty()) {
            //返回栈顶元素
            return top.data ;
        }else {
            return null ;
        }
    }
    //入栈
    @Override
    public void push(Object x) throws Exception {
        //构造一个新结点
        Node p = new Node(x) ;
        p.next = top ;          //p的指针域指向栈顶元素
        top = p ;               //新结点成为当前的栈顶元素
    }
    //出栈
    @Override
    public Object pop() {
        if (isEmpty()) {
            return null ;
        }else {
            Node p = top ;          //p指向被删除的结点（栈顶元素）。 用于记录被删除的结点，以便返回删除的值
            top = top.next ;        //修改链指针，使栈顶结点从链栈中移去
            return p.data ;         //返回栈顶结点的数据域值
        }
    }
    //输出栈中所有数据元素（从栈顶元素到栈底元素）
    public void display() {
        Node p = top ;          //初始化，p指向栈顶元素
        while (p != null ) {    //输出所有非空结点的数据元素值
            System.out.print(p.data.toString()+" ");
            p = p.next ;        //p指针向后移
        }
    }
}

package data.linear_table.test;
import data.linear_table.stack_queue.LinkStack;
//将算术表达式转换为后缀表达式的函数，结果以字符串的形式进行返回
    //expression 参数为要转换的算术表达式
    public String convertToPostFix(String expression) throws Exception {
        LinkStack st = new LinkStack();     //初始化一个运算符栈
        String postfix = new String();     //用于存放输出的后缀表达式
        for (int i = 0; expression != null && i < expression.length(); i++) {
            char c = expression.charAt(i);      //从算术表达式中读取一个字符
            if (c != ' ') {         //判断c不为空格
                if (isOpenParenthesis(c)) {
                    //为开括号 '（ ',压栈
                    st.push(c);
                } else if (isCloseParenthesis(c)) {
                    //为闭括号 ' ) ' ,弹出
                    char ac = (Character) st.pop();         //强制类型转换，弹出栈顶元素；
                    while (!isOpenParenthesis(ac)) {       //循环一直到ac为开括号 （ 为止
                        postfix = postfix.concat(String.valueOf(ac));       //串联到后缀表达式的结尾
                        ac = (Character) st.pop();          //继续弹出元素
                    }
                } else if (isOperator(c)) {
                    //为运算符时
                    if (!st.isEmpty()) {       //判断栈非空时，取出栈顶优先级高的运算符送往后缀表达式
                        Character ac = (Character) st.pop();
                        while (ac!=null && priority(ac.charValue()) >= priority(c)) {
                            postfix = postfix.concat(String.valueOf(ac));   //串联到后缀表达式的结尾
                            ac = (Character) st.pop();         //继续弹出
                        }
                        if (ac != null) {    //若最后一次取出的优先级低的操作符，重新压栈
                            st.push(ac);
                        }
                    }
                    st.push(c);  //压栈
                }else {
                    //为操作数
                    postfix = postfix.concat(String.valueOf(c));       //串联到后缀表达式的结尾
                }
            }
        }
        while (! st.isEmpty()) {        //栈中剩余所有的操作符，串联到后缀表达式结尾
            postfix = postfix.concat(String.valueOf(st.pop())) ;
        }
        return postfix ;
    }

 //判断字符串是否为运算符
    public boolean isOperator(char c) {
        //判断c是否等于 +-*/^ %
        if ('+' == c || '-' == c || '*' == c || '/' == c || '^' == c || '%' == c) {
            return true ;
        }else {
            return false ;
        }
    }

 //判断字符串是否为运算符
    public boolean isOperator(char c) {
        //判断c是否等于 +-*/^ %
        if ('+' == c || '-' == c || '*' == c || '/' == c || '^' == c || '%' == c) {
            return true ;
        }else {
            return false ;
        }
    }

 //判断字符串是否为开括号
    public boolean isOpenParenthesis (char c) {
        return '(' == c ;
    }

 //判断字符串是否为闭括号
    public boolean isCloseParenthesis(char c) {
        return ')' == c ;
    }

   //判断运算法的优先级
    public int priority(char c) {
        if (c == '^') {     //为幂运算
            return 3 ;
        }
        if (c == '*' || c == '/' || c == '%' ) {        //为乘除，取模运算
            return 2 ;
        }else  if (c == '+' || c == '-') {              //为加减运算
            return 1 ;
        }else {                                         //其他运算
            return 0 ;
        }
    }
}

package data.linear_table.test;
public class Example3_Text {
    public static void main(String[] args) throws Exception {
        //创建后缀表达式，计算值类
        Example3 p = new Example3();
        //调用方法转换为后缀表达式
        String postfix = p.convertToPostFix("(1+2)*(5-2)/2^2+5%3");
        System.out.println("转换的后缀表达式为："+postfix);
        //对后缀表达式求值，并输出
        System.out.println("计算后缀表达式的结果为：" + p.numberCalculate(postfix));
    }
}