Java 示例 - 中缀到后缀
-
问题描述
如何将中缀表达式转换为后缀表达式? -
解决方案
以下示例演示了如何使用堆栈的概念将中缀转换为后缀表达式。import java.io.IOException; public class InToPost { private Stack theStack; private String input; private String output = ""; public InToPost(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; InToPost theTrans = new InToPost(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/+
以下是将中缀表达式转换为后缀表达式的另一个示例示例。import java.io.BufferedReader; import java.io.InputStreamReader; class stack { 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 Demo { public static void main(String[] args)throws Exception { String s; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); stack b = new stack(); 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); } }
上面的代码示例将产生以下结果。Enter input string 124*5/+7-36/+ Input String:124*5/+7-36/+ Output String: 12*/-3/675