表达式求值

##从学了数据结构之后好久了,今天准备回忆一下基本的一些算法

在开头先讲讲有关的一些东西

1. 前缀表达式

 前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是,其将运算符写在前面,操作数写在后面

2. 中缀表达式

 中缀表达式(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。
 与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。
 与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来,用于指示运算的次序。

3. 后缀表达式

 后缀表达式,又称逆波兰式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

在了解来什么是前缀、中缀、后缀表达式之后,开始实现一个万能的表达式求值

算法的原理就是运用了栈的先进后出的特性

在此之前,先准备好栈的实现,我是运用了链表来实现栈结构

/**
 * 栈的实现接口,规定了栈的主要方法
 * @param <T>
 */
interface Stack<T> {

    public T push(T data);

    public T pop();

    public T peek();

    public boolean isEmpty();

    public int size();
}

/**
 * 自定义结点类
 * @param <T>
 */
class Node<T> {
    T dataT;
    Node<T> nextNode;

    public T getDataT() {
        return dataT;
    }

    public void setDataT(T dataT) {
        this.dataT = dataT;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    public Node(T dataT) {
        this.dataT = dataT;
        this.nextNode = null;
    }

    public Node() {
        super();
    }
}

/**
 * 实现Stack<T>接口,运用链表实现栈的基本方法
 * @param <T>
 */
class LinkedStack<T> implements Stack<T> {

    private int size;       //栈的大小
    private Node<T> top;    //栈顶指针

    public LinkedStack() {
        size = 0;
        top = null;
    }

    /**
     * 进行入栈操作,先判断栈是否为空,如果为空,直接入栈,否则,用头插的方式将新结点插入链表头部
     * @param data
     * @return
     */
    public T push(T data) {
        Node<T> newNode = new Node<T>(data);
        if (!isEmpty()) {
            newNode.setNextNode(top);
            top = newNode;
        } else {
            top = newNode;
        }
        size++;
        return data;
    }

    /**
     * 出栈操作,将栈顶元素弹出,同时删除栈顶元素,这里就是讲链表头部的数据return,栈顶指针向后移动
     * @return 栈顶元素
     */
    public T pop() {
        T iT;
        if (!isEmpty()) {
            iT = top.getDataT();
            top = top.getNextNode();
            size--;
            return iT;
        } else {
            return null;
        }
    }

    /**
     *查看栈顶元素,不弹出
     * @return 栈顶元素
     */
    public T peek() {
        T iT;
        if (!isEmpty()) {
            iT = top.getDataT();
            return iT;
        } else {
            return null;
        }
    }

    /**
     * 判断栈是否为空,就是判断栈顶指针是否为空以及栈的大小是否为0
     * @return
     */
    public boolean isEmpty() {
        if ((top == null) && (size == 0)) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 返回栈的大小
     * @return
     */
    public int size() {
        return size;
    }
}

有了栈的实现类之后,就可以开始了

1. 先解析表达式

因为表达式可能含有括号,带小数的数字,符号等等,所以在计算之前,我们要先将表达式解析一遍。这里运用的是**ArrayList**来存每一个解析后的值,代码如下:

/**
 * 解析表达式
 *
 * @param str
 * @return
 */
public static ArrayList<String> analysisExpression(String str) {
    ArrayList<String> list = new ArrayList<String>();
    char[] arr = str.toCharArray();
    StringBuffer tmpStr = new StringBuffer();
    for (char c : arr) {
        if ((c >= '0') && (c <= '9') || (c == '.')) {
            tmpStr.append(c);
        } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
              if (tmpStr.length() > 0) {
                  list.add(tmpStr.toString());
                  tmpStr.setLength(0);
              }
              list.add(c + "");
        }
    }
    if (tmpStr.length() > 0) {
        list.add(tmpStr.toString());
    }
    return list;
}
2.解析了表达式之后,这里我们是将中缀表达式转换成了后缀,个人觉得因为后缀表达式计算方便,也可以直接将中缀表达式直接求值,代码如下:
/**
 * 中缀转后缀
 * infix转suffix
 * @param list
 * @return 后缀表达式
 */
public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
    ArrayList<String> strList = new ArrayList<String>();
    LinkedStack<String> stack = new LinkedStack<String>();
    String tmp;
    for (String s : list) {
        if (s.equals("(")) {
            stack.push(s);
        } else if (s.equals(")")) {
            while (!(tmp = stack.pop()).equals("(")) {
                strList.add(tmp);
            }
        } else if (s.equals("*") || s.equals("/")) {
            while (!stack.isEmpty()) {
                tmp = stack.peek();
                if (tmp.equals("*") || tmp.equals("/")) {
                    stack.pop();
                    strList.add(tmp);
                } else {
                    break;
                }
            }
            stack.push(s);
        } else if (s.equals("+") || s.equals("-")) {
            while (!stack.isEmpty()) {
                tmp = stack.peek();
                if (!tmp.equals("(")) {
                    stack.pop();
                    strList.add(tmp);
                } else {
                    break;
                }
            }
            stack.push(s);
        } else {
            strList.add(s);
        }
    }
    while (!stack.isEmpty()) {
        strList.add(stack.pop());
    }
    return strList;
}
3.装换成后缀之后,那么计算就十分方便了
/**
 * 计算后缀表达式的值
 *
 * @param 后缀表达式
 * @return 最终结果的值
 */
public static double Calculate(ArrayList<String> strList) {
    LinkedStack<Double> newStack = new LinkedStack<Double>();
    for (String s : strList) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            double b1 = newStack.pop();
            double b2 = newStack.pop();
            if (s.equals("+")) {
                newStack.push(b2 + b1);
            } else if (s.equals("-")) {
                newStack.push(b2 - b1);
            } else if (s.equals("*")) {
                newStack.push(b2 * b1);
            } else if (s.equals("/")) {
                newStack.push(b2 / b1);
            }
        } else {
            newStack.push(Double.valueOf(s));
        }
    }
    return newStack.peek();
}

最后的代码如下:

import java.util.ArrayList;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        String str = "(3+5)*3/3+9-(8-2.3)*5";   //算出来结果为-11.5
        Double result = Calculate(infixToSuffix(analysisExpression(str)));
        System.out.println("表达式为:"+str);
        System.out.println("结果为:"+result);
    }

/**
 * 解析表达式
 *
 * @param str
 * @return
 */
public static ArrayList<String> analysisExpression(String str) {
    ArrayList<String> list = new ArrayList<String>();
    char[] arr = str.toCharArray();
    StringBuffer tmpStr = new StringBuffer();
    for (char c : arr) {
        if ((c >= '0') && (c <= '9') || (c == '.')) {
            tmpStr.append(c);
        } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
              if (tmpStr.length() > 0) {
                  list.add(tmpStr.toString());
                  tmpStr.setLength(0);
              }
              list.add(c + "");
        }
    }
    if (tmpStr.length() > 0) {
        list.add(tmpStr.toString());
    }
    return list;
}

/**
 * 中缀转后缀
 * infix转suffix
 * @param list
 * @return 后缀表达式
 */
public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
    ArrayList<String> strList = new ArrayList<String>();
    LinkedStack<String> stack = new LinkedStack<String>();
    String tmp;
    for (String s : list) {
        if (s.equals("(")) {
            stack.push(s);
        } else if (s.equals(")")) {
            while (!(tmp = stack.pop()).equals("(")) {
                strList.add(tmp);
            }
        } else if (s.equals("*") || s.equals("/")) {
            while (!stack.isEmpty()) {
                tmp = stack.peek();
                if (tmp.equals("*") || tmp.equals("/")) {
                    stack.pop();
                    strList.add(tmp);
                } else {
                    break;
                }
            }
            stack.push(s);
        } else if (s.equals("+") || s.equals("-")) {
            while (!stack.isEmpty()) {
                tmp = stack.peek();
                if (!tmp.equals("(")) {
                    stack.pop();
                    strList.add(tmp);
                } else {
                    break;
                }
            }
            stack.push(s);
        } else {
            strList.add(s);
        }
    }
    while (!stack.isEmpty()) {
        strList.add(stack.pop());
    }
    return strList;
}
/**
 * 计算后缀表达式的值
 *
 * @param 后缀表达式
 * @return 最终结果的值
 */
public static double Calculate(ArrayList<String> strList) {
    LinkedStack<Double> newStack = new LinkedStack<Double>();
    for (String s : strList) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            double b1 = newStack.pop();
            double b2 = newStack.pop();
            if (s.equals("+")) {
                newStack.push(b2 + b1);
            } else if (s.equals("-")) {
                newStack.push(b2 - b1);
            } else if (s.equals("*")) {
                newStack.push(b2 * b1);
            } else if (s.equals("/")) {
                newStack.push(b2 / b1);
            }
        } else {
            newStack.push(Double.valueOf(s));
        }
    }
    return newStack.peek();
}

/**
 * 栈的实现接口,规定了栈的主要方法
 *
 * @param <T>
 */
interface Stack<T> {

    public T push(T data);

    public T pop();

    public T peek();

    public boolean isEmpty();

    public int size();
}

/**
 * 自定义结点类
 * @param <T>
 */
class Node<T> {
    T dataT;
    Node<T> nextNode;

    public T getDataT() {
        return dataT;
    }

    public void setDataT(T dataT) {
        this.dataT = dataT;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    public Node(T dataT) {
        this.dataT = dataT;
        this.nextNode = null;
    }

    public Node() {
        super();
    }
}


示例结果输出:

表达式为:(3+5)*3/3+9-(8-2.3)*5
结果为:-11.5

总结

算法实现其实并不难,但是细节非常多,很容易出错

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/2019081192525
最后更新于:2020-02-26 16:20:41

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×