中缀表达式转后缀表达式的思路

1) 初始化两个字符串栈:运算符栈 operStack 和储存中间结果的栈 numStack
2) 从左至右扫描中缀表达式;
3) 遇到操作数时,将其直接压入 numStack
4) 遇到运算符时,比较其与 operStack 栈顶运算符的优先级:

  • 如果 operStack 为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈operStack
  • 否则,若当前运算符的优先级比栈顶运算符的优先级高,则将当前运算符压入 operStack
  • 否则,若栈顶的运算符优先级高于或等于当前的运算符的优先级,则将 operStack 栈顶的运算符弹出并压入到 numStack 中,再次转到(4)与 operStack 中新的栈顶运算符相比较;

5)遇到括号时:

  • 如果是左括号“(”,则直接压入 operStack
  • 如果是右括号“)”,则依次弹出 operStack 栈顶的运算符,并压入 numStack,直到遇到左括号为止,此时将这一对括号同时丢弃。即在while循环完成判断后,再operStack.pop();

6) 重复步骤 2 至 5,直到表达式的最右边
7) 将 operStack 中剩余的运算符依次弹出并压入 numStack
8) 依次弹出 numStack 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式,也可直接使用List<String> ,则无需进行逆置。

代码实现

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

public class PolandExer {
    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpression(expression);
        System.out.println(infixExpressionList);
        List<String> result = parseSuffixExpression(infixExpressionList);
        System.out.println(result);
    }

    /**
     * 将中缀表达式转换为对应的List
     * 
     * @param 欲转换的字符串
     * @return 返回List
     */
    public static List<String> toInfixExpression(String s) {
        // 生成一个List,用于存放拆分的内容
        List<String> ls = new ArrayList<String>();
        // 指针,用来充当索引
        int i = 0;
        // 每遍历到一个字符,就放到ls中
        char c;
        // str 用于拼合数字
        String str;
        do {
            // 如果c是一个非数字,则直接加入到ls中
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {
                // 如果c是一个数字,需要继续判断是否属于多位数的情况
                str = "";
                // 通过循环,找到完整多位数
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }

    public static List<String> parseSuffixExpression(List<String> ls) {
        Stack<String> operStack = new Stack<String>();
        List<String> numStack = new ArrayList<String>();

        // 遍历ls
        for (String item : ls) {
            // 如果是一个数,就直接加到numStack;
            if (item.matches("\\d+")) {
                numStack.add(item);
            } else if (item.equals("(")) {
                operStack.push(item);
            } else if (item.equals(")")) {
                while (!operStack.peek().equals("(")) {
                    numStack.add(operStack.pop());
                }
                operStack.pop();
            } else {
                while (operStack.size()!=0&&Operation.getWeights(item)<=Operation.getWeights(operStack.peek())) {
                    numStack.add(operStack.pop());
                }
                operStack.push(item);
            }
        }
        while (operStack.size()!=0) {
            numStack.add(operStack.pop());
        }
        return numStack;
    }
}

class Operation {
    /**
     * 计算运算符的权重
     * @param operation
     * @return
     */
    public static int getWeights(String operation) {
        // 权重
        int Weights = 0;
        switch (operation) {
            case "+":
                Weights = 1;
                break;
            case "-":
                Weights = 1;
                break;
            case "*":
                Weights = 2;
                break;
            case "/":
                Weights = 1;
                break;
            default:
            //System.out.println("error:运算符不合法!");
            //因为else进行判断,出现其他符合也会出现不合法的提示
                break;
        }
        return Weights;
    }
}

PolandExer.zip

Last modification:December 14th, 2020 at 12:56 am
如果觉得我的文章对你有用,请随意赞赏