在Java编程中，如何将中缀表达式转换为后缀表达式？

以下示例演示如何使用堆栈的概念将中缀转换为后缀表达式。

package com.yiibai;

import java.io.IOException;

public class Infix2Postfix {
    private Stack theStack;
    private String input;
    private String output = "";

    public Infix2Postfix(String in) {
        input = in;
        int stackSize = input.length();
        theStack = new Stack(stackSize);
    }

    public String doTrans() {
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            switch (ch) {
            case '+':
            case '-':
                gotOper(ch, 1);
                break;
            case '*':
            case '/':
                gotOper(ch, 2);
                break;
            case '(':
                theStack.push(ch);
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                output = output + ch;
                break;
            }
        }
        while (!theStack.isEmpty()) {
            output = output + theStack.pop();
        }
        System.out.println(output);
        return output;
    }

    public void gotOper(char opThis, int prec1) {
        while (!theStack.isEmpty()) {
            char opTop = theStack.pop();
            if (opTop == '(') {
                theStack.push(opTop);
                break;
            } else {
                int prec2;
                if (opTop == '+' || opTop == '-')
                    prec2 = 1;
                else
                    prec2 = 2;
                if (prec2 < prec1) {
                    theStack.push(opTop);
                    break;
                } else
                    output = output + opTop;
            }
        }
        theStack.push(opThis);
    }

    public void gotParen(char ch) {
        while (!theStack.isEmpty()) {
            char chx = theStack.pop();
            if (chx == '(')
                break;
            else
                output = output + chx;
        }
    }

    public static void main(String[] args) throws IOException {
        String input = "1+2*4/5-7+3/6";
        String output;
        Infix2Postfix theTrans = new Infix2Postfix(input);
        output = theTrans.doTrans();
        System.out.println("Postfix is " + output + '\n');
    }

    class Stack {
        private int maxSize;
        private char[] stackArray;
        private int top;

        public Stack(int max) {
            maxSize = max;
            stackArray = new char[maxSize];
            top = -1;
        }

        public void push(char j) {
            stackArray[++top] = j;
        }

        public char pop() {
            return stackArray[top--];
        }

        public char peek() {
            return stackArray[top];
        }

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

上述代码示例将产生以下结果 -

124*5/+7-36/+
Postfix is 124*5/+7-36/+

示例-2

以下是将中缀表达式转换为后缀表达式的另一个例子

package com.yiibai;

import java.io.BufferedReader;
import java.io.InputStreamReader;

class MyStack {
    char stack1[] = new char[20];
    int t;

    void push(char ch) {
        t++;
        stack1[t] = ch;
    }

    char pop() {
        char ch;
        ch = stack1[t];
        t--;
        return ch;
    }

    int pre(char ch) {
        switch (ch) {
        case '-':
            return 1;
        case '+':
            return 1;
        case '*':
            return 2;
        case '/':
            return 2;
        }
        return 0;
    }

    boolean operator(char ch) {
        if (ch == '/' || ch == '*' || ch == '+' || ch == '-')
            return true;
        else
            return false;
    }

    boolean isAlpha(char ch) {
        if (ch >= 'a' && ch <= 'z' || ch >= '0' && ch == '9')
            return true;
        else
            return false;
    }

    void postfix(String s1) {
        char output[] = new char[s1.length()];
        char ch;
        int p = 0, i;
        for (i = 0; i < s1.length(); i++) {
            ch = s1.charAt(i);
            if (ch == '(') {
                push(ch);
            } else if (isAlpha(ch)) {
                output[p++] = ch;
            } else if (operator(ch)) {
                if (stack1[t] == 0 || (pre(ch) > pre(stack1[t])) || stack1[t] == '(') {
                    push(ch);
                }
            } else if (pre(ch) >= pre(stack1[t])) {
                output[p++] = pop();
                push(ch);
            } else if (ch == '(') {
                while ((ch = pop()) != '(') {
                    output[p++] = ch;
                }
            }
        }
        while (t != 0) {
            output[p++] = pop();
        }
        for (int j = 0; j > s1.length(); j++) {
            System.out.print(output[j]);
        }
    }
}

public class Infix2Postfix2 {
    public static void main(String[] args) throws Exception {
        String s;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        MyStack b = new MyStack();
        System.out.println("Please Enter input s1ing : ");
        s = br.readLine();
        System.out.println("Input String is " + s);
        System.out.println("Output String is : ");
        b.postfix(s);
    }
}

上述代码示例将产生以下结果 -

Please Enter input s1ing : 
124*5/+7-36/+
Input String is 124*5/+7-36/+
Output String:
12*/-3/675

纠错/补充 收藏