算法4 1.3.11

求值一个后序表达式

将中序表达式转换为后序表达式：

// 转换为后序表达式
static String[] infixToPostfix(String str)
{
    LinkStack<String> valStack = new LinkStack<>();
    LinkStack<String> opStack = new LinkStack<>();
    char[] chars = str.toCharArray();

    for (int i = 0; i < chars.length; i++)
    {
        char c = chars[i];
        if (c == '(')
        {
            opStack.push(String.valueOf(chars[i]));
        }
        else if (c == '+' || c == '-')
        {
            if (!opStack.isEmpty())
            {
                String topOp = opStack.peek();
                if (!topOp.equals("("))
                {
                    String v2 = valStack.pop();
                    String v1 = valStack.pop();
                    String op = opStack.pop();
                    String s = v1 + " " + v2 + " " + op;
                    valStack.push(s);
                }

                opStack.push(String.valueOf(chars[i]));
            }
            else
            {
                opStack.push(String.valueOf(chars[i]));
            }
        }
        else if (c == '*' || c == '/')
        {
            if (!opStack.isEmpty())
            {
                String topOp = opStack.peek();

                if (topOp.equals("+") || topOp.equals("-"))
                {
                    opStack.push(String.valueOf(chars[i]));
                }
                else
                {
                    String v2 = valStack.pop();
                    String v1 = valStack.pop();
                    String op = opStack.pop();
                    String s = v1 + " " + v2 + " " + op;
                    valStack.push(s);
                    opStack.push(String.valueOf(chars[i]));
                }
            }
            else
            {
                opStack.push(String.valueOf(chars[i]));
            }
        }
        else if (c == ')')
        {
            String v2 = valStack.pop();
            String v1 = valStack.pop();
            String op2 = opStack.pop();
            String op1 = opStack.pop();
            String s = v1 + " " + v2 + " " + op2;
            valStack.push(s);
        }
        else
        {
            valStack.push(String.valueOf(chars[i]));
        }
    }

    while (!opStack.isEmpty())
    {
        String op = opStack.pop();
        String val2 = valStack.pop();
        String val1 = valStack.pop();
        String s = val1 + " " + val2 + " " + op;
        valStack.push(s);
    }

    String[] result = valStack.pop().split(" ");

    return result;
}

例如：中序表达式：1-(1+2+3)*(3-4)+5转换为后序表达式为：1 1 2 + 3 + 3 4 - * 5 + -，那么求它的值，依次将表达式入栈，遇到运算符，出栈2个元素，计算后重新入栈即可，最后栈顶元素就是表达式的值：

// 对后序表达式求值
static void evaluatePostfix()
{
    String str = "1-(1+2+3)*(3-4)+5";
    String[] result = infixToPostfix(str);
    System.out.println("str: " + str + " , 后序表达式为：" + String.join(" ", result));

    LinkStack<Integer> stack = new LinkStack<>();
    for (int i = 0; i < result.length; i++)
    {
        String c = result[i];
        if (c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/"))
        {
            int v2 = stack.pop();
            int v1 = stack.pop();
            if (c.equals("+"))
            {
                stack.push(v1 + v2);
            }
            else if (c.equals("-"))
            {
                stack.push(v1 - v2);
            }
            else if (c.equals("*"))
            {
                stack.push(v1 * v2);
            }
            else if (c.equals("/"))
            {
                stack.push(v1 / v2);
            }
        }
        else
        {
            stack.push(Integer.valueOf(String.valueOf(c)));
        }
    }
    System.out.println("计算结果为：" + stack.pop());
}

结果：

str: 1-(1+2+3)*(3-4)+5 , 后序表达式为：1 1 2 + 3 + 3 4 - * 5 + -
计算结果为：2