使用栈结构计算表达式的值

使用栈结构计算表达式的值

1.现在给定一个中缀表达式(infixExpression) 使用栈结构计算它的值

package pers.amos.learn.review.stack;


/**
 * @author amos wong
 * @create 2019-12-01 19:29
 */

public class CalculatorReviewDemo {
    public static void main(String[] args) {
        String expression = "90+2*6-2"; // 需要计算的语句
        int res = CalculatorReview.calculate(expression);
        System.out.printf("res=[%d]", res);
    }


}

class CalculatorReview {

    public static int calculate(String infixExpression) {
        int index = 0;
        int res = 0;
        String keepNum = "";
        char ch;
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operaStack = new ArrayStack2(10);
        while (index < infixExpression.length()) {
            ch = infixExpression.substring(index, index + 1).charAt(0);
            if (!numStack.isOperator(ch)) {
                if (index == infixExpression.length() - 1) {
                    numStack.push(ch - '0');
                } else {
                    keepNum += ch;
                    if (numStack.isOperator(infixExpression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            } else {
                if (operaStack.isEmpty()) {
                    operaStack.push(ch);
                } else if (operaStack.priority(ch) <= operaStack.priority(operaStack.peek())) {
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    int operator = operaStack.pop();
                    res = numStack.calculate(num1, num2, operator);
                    numStack.push(res);
                    operaStack.push(ch);
                } else {
                    operaStack.push(ch);
                }
            }
            index++;
        }
        while (!operaStack.isEmpty()) {
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int operator = operaStack.pop();
            res = numStack.calculate(num1, num2, operator);
            numStack.push(res);
        }
        return numStack.pop();
    }
}

class ArrayStack2 {
    private int maxSize;
    private int top = -1; // 栈顶未添加数据之前为-1
    private int[] data;

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        data = new int[maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 获取但不移除栈顶元素
     */
    public int peek() {
        return data[top];
    }

    /**
     * 入栈
     *
     * @param value
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        data[top] = value;
    }

    /**
     * 出栈
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空..");
        }
        int value = data[top];
        top--;
        return value;
    }

    /**
     * 遍历栈
     * 从栈顶向下遍历
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("栈为空");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("栈的元素为data[%d]=%d\n", i, data[i]);
        }
    }

    /**
     * 判断符号的优先级
     * 假设只有 +、-、*、/ 这四种运算符
     *
     * @param operator
     * @return
     */
    public int priority(int operator) {
        if (operator == '+' || operator == '-') {
            return 0;
        } else if (operator == '*' || operator == '/') {
            return 1;
        } else {
            return -1; // 其他符号不认识 返回-1
        }
    }

    /**
     * 判断是否为运算符
     *
     * @param operator
     * @return
     */
    public boolean isOperator(char operator) {
        return operator == '+' || operator == '-' || operator == '*' || operator == '/';
    }

    /**
     * 根据操作数计算两个数的运算结果 在进行/和-时注意顺序 应该num2在前面 num1在后面
     *
     * @param num1     后被压入栈的数
     * @param num2     先被压入栈的数
     * @param operator
     * @return
     */
    public int calculate(int num1, int num2, int operator) {
        int res = 0;
        if (operator == '+') {
            res = num1 + num2;
        } else if (operator == '-') {
            res = num2 - num1;
        } else if (operator == '*') {
            res = num1 * num2;
        } else {
            res = num2 / num1;
        }
        return res;
    }
}

需要注意的是:

  • 表达式中的数字可能是一个多位数,如果仅仅判断为ch这一个字符为数字就压入numStack显然不合理,所以需要将当前的ch先暂存到keepNum字符串中,然后继续往后遍历一位,如果后面这一位是数字则继续存到KeepNum中,直到遍历到后面那一位是运算符为止。最后再将keepNum转化为数值压入numStack
  • 将keepNum压入栈后,需要将keepNum置空
  • 其中还需要注意的是如果ch为表达式的最后一位 应该直接压入numStack中
if (!numStack.isOperator(ch)) {
                if (index == infixExpression.length() - 1) {
                    numStack.push(ch - '0');
                } else {
                    keepNum += ch;
                    if (numStack.isOperator(infixExpression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            }

2.使用给定的后缀表达式计算运行结果

package pers.amos.learn.review.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author amos wong
 * @create 2019-12-01 20:56
 */

public class PolandNotationReview {
    public static void main(String[] args) {
        String suffixExpression = "3 4 + 5 * 6 -";
        List<String> suffixList = Calculator.suffixExpressionToList(suffixExpression);
        System.out.println("后缀表达式转化为list" + suffixList);
        int res = Calculator.calculate(suffixList);
        System.out.println("后缀表达式的运算结果为:" + res);
    }
}

/**
 * 计算后缀表达式的值
 */

class Calculator {
    public static int calculate(List<String> suffixList) {
        Stack<String> stack = new Stack<>();
        int res = 0;
        for (String item : suffixList) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                String num1 = stack.pop();
                String num2 = stack.pop();
                res = calculate(num1, num2, item);
                stack.push(res + "");
            }
        }
        return res;
    }

    /**
     * 将后缀表达式转化为list便于迭代
     *
     * @param suffixExpression
     * @return
     */
    public static List<String> suffixExpressionToList(String suffixExpression) {
        String[] expression = suffixExpression.split(" ");
        List<String> suffixList = new ArrayList<>();
        for (String item : expression) {
            suffixList.add(item);
        }
        return suffixList;
    }

    public static int calculate(String num1, String num2, String operator) {
        int res = 0;
        if (operator.equals("+")) {
            res = Integer.parseInt(num1) + Integer.parseInt(num2);
        } else if (operator.equals("-")) {
            res = Integer.parseInt(num2) - Integer.parseInt(num1); //注意运算顺序
        } else if (operator.equals("*")) {
            res = Integer.parseInt(num1) * Integer.parseInt(num2); 
        } else if (operator.equals("/")) {
            res = Integer.parseInt(num2) / Integer.parseInt(num1); //注意运算顺序
        }
        return res;
    }
}

需要注意的是:

  • calculate()中 - 和 / 的运算顺序
  • 先出栈的是减数/除数 后出栈的是被减数/被除数

评论

Your browser is out-of-date!

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

×