1.3.10中序表达式转换为后序表达式

表达式都是括号的形式

后序表达式 算术运算符在尾部，例如： 1 + 2的后序形式：1 2 +，后序表达式是没有括号的，所以转换的结果它是有操作符优先级的，例如:2 + 3 * 4，它的后序表达式为：2 3 4 * +，这个题如果假设所有的表达式都包括括号的话，如((1+2)*(4-3))，它转换为后序表达式：1 2 + 4 3 - *，我们还是valStack保存数字，opStack保存算术运算符。

遍历表达式，对于+，-,*, /，压入opStack，对于数字或(压入valStack，而碰到)，取出两个数字，一个运算符，组合成字符串，压入栈：

for (int i = 0; i < chars.length; i++)
{
    if (chars[i] == '+' || chars[i] == '-' || chars[i] == '*' || chars[i] == '/')
    {
        opStack.push(String.valueOf(chars[i]));
    }
    else if (chars[i] == ')')
    {
        String op = opStack.pop();
        String val2 = valStack.pop();
        String val1 = valStack.pop();
        String val0 = valStack.pop();

        String s = val1 + " " + val2 + " " + op;
        System.out.println("入栈字符串：" + s);
        valStack.push(s);
    }
    else
    {
        valStack.push(String.valueOf(chars[i]));
    }
}

那么现在valStack上都是每个括号组成的子表达式，我们依次出栈，拼装成字符串，就是我们要的结果：

while (!valStack.isEmpty())
{
    listStr = valStack.pop() + listStr;
}
System.out.println(listStr);

完整源码：

static void test1()
{
    LinkStack<String> valStack = new LinkStack<>();
    LinkStack<String> opStack = new LinkStack<>();
    String listStr = "";
    String str = "((1+2)*((3-4)*(5-6)))";
    str = "((1+2)*(4-3))";
    char[] chars = str.toCharArray();

    for (int i = 0; i < chars.length; i++)
    {
        if (chars[i] == '+' || chars[i] == '-' || chars[i] == '*' || chars[i] == '/')
        {
            opStack.push(String.valueOf(chars[i]));
        }
        else if (chars[i] == ')')
        {
            String op = opStack.pop();
            String val2 = valStack.pop();
            String val1 = valStack.pop();
            String val0 = valStack.pop();

            String s = val1 + " " + val2 + " " + op;
            System.out.println("入栈字符串：" + s);
            valStack.push(s);
        }
        else
        {
            valStack.push(String.valueOf(chars[i]));
        }
    }

    while (!valStack.isEmpty())
    {
        listStr = valStack.pop() + listStr;
    }
    System.out.println(listStr);
}

普通模式

它可以有括号，也可以没有，例如：(1+2)*(3-4)，它的1 2 + 3 4 - *：

加入括号，比较麻烦也比较困难，所以循序渐进，我们先处理没有括号的情况，1 + 2 * 4，按照转换规则，应该先计算 2 * 4，然后1 + 这个结果，将数字存到valStack，运算符存到opStack，当运算符要入栈前，如果当前运算符比栈顶的优先级低，则对opStack出栈，对valStack出栈两个数字，将这些数字组合成子运算，重新入栈，并对当前运算符入栈：

for (int i = 0; i < chars.length; i++)
{
    char c = chars[i];
    if (c == '+' || c == '-')
    {
        if (!opStack.isEmpty())
        {
            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
    {
        valStack.push(String.valueOf(chars[i]));
    }
    //System.out.println("");
}

这样opStack有一个运算符，对其出栈，然后对valStack出栈两个数字，直到opStack为空：

while (!opStack.isEmpty())
{
    String op = opStack.pop();
    String val2 = valStack.pop();
    String val1 = valStack.pop();
    String s = val1 + " " + val2 + " " + op;
    valStack.push(s);
    //System.out.println("输出s: " + s);
}

System.out.println("str: " + str + " , 后序表达式为：" + valStack.peek());

valStack栈顶就是最终的字符串：

现在来考虑有括号的情况

根据我的一番思索，在前述没有括号的情况下扩展，(可以看做是优先级最低的的算术操作符，)是优先级最高的操作符，当前算术运算符低于栈顶的话，就进行出栈。两个括号都存到opStack栈上，对于+、-，判断栈是否为空，栈顶如果是(，表示当前是一个括号中的表达式，所以不能出栈，如果不是的话，进行出栈再入栈。

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]));
    }
}

然后对opStack出栈，同时对valStack出栈2次，待opStack出栈完毕后，栈顶就是最终的表达式。

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

System.out.println("str: " + str + " , 后序表达式为：" + valStack.peek());

全部源码：

static void test3()
{
    LinkStack<String> valStack = new LinkStack<>();
    LinkStack<String> opStack = new LinkStack<>();
    String str = "((1+2)*((3-4)*(5-6)))";
    str = "(1+2+3)*(3-4)+5";
    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);
    }

    System.out.println("str: " + str + " , 后序表达式为：" + valStack.peek());
}

输出信息：

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