java中的中缀到后缀的转换
Infix to postfix conversion in java
我有一个 java class 可以将中缀表达式转换为后缀。我设法使 class 运行 没有错误，但它没有给我正确的输出。输出的格式应该是 :
InToPost: converting expressions from infix to postfix...
[A, +,
B]
[A, +, B, *, C]
[A, +, B, *, C, +, D]
[(, A, +, B, ),
*, C]
[(, A, +, B, ), /, (, C, -, D, )]
[(, (, A, +, B, ), *, C, -, (, D, -, E, ), )]
InToPost: emitting postfix
expressions...
A B +
A B C * +
A B C * + D +
A B + C
*
A B + C D - /
A B + C * D E - -
但我的输出是：
InToPost: converting expressions from infix to postfix... [A, +,
B]
[A, +, B, *, C]
[A, +, B, *, C, +, D]
[(, A, +, B, ),
*, C]
[(, A, +, B, ), /, (, C, -, D, )]
[(, (, A, +, B, ), , C, -, (, D, -, E, ), )]
InToPost: emitting postfix expressions...
A+B
A+BC
A+B*C+D
(A+B)*C
(A+B)/(C-D)
((A+B)*C-(D-E))
转换方法如下：
private List<String> convert(List<String> tokens) {
// YOUR IMPLEMENTATION HERE
StackNode opstack = new StackNode();
//List<Object> postfix = new ArrayList<Object>();
//int sizeOfList=tokens.size();
String postfixString = " ";
for (int index = 0; index < tokens.size(); ++index) {
String chValue = tokens.get(index);
if (chValue == "(") {
opstack.push("(");
} else if (chValue == ")") {
String oper = String.valueOf(opstack.top());
while (!(oper.equals("(")) && !(opstack.empty())) {
postfixString += oper;
opstack.pop();
oper = String.valueOf(opstack.top());
}
opstack.pop();
} else if (chValue == "+" || chValue == "-") {
//Stack is empty
if (opstack.empty()) {
opstack.push(chValue);
//current Stack is not empty
} else {
String oper = String.valueOf(opstack.top());
while (!(opstack.empty() || oper.equals(new String("(")) || oper.equals(new String(")")))) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else if (chValue == "*" || chValue == "/") {
if (opstack.empty()) {
opstack.push(chValue);
} else {
String oper = String.valueOf(opstack.top());
while (!oper.equals(new String("+")) && !oper.equals(new String("-")) && !opstack.empty()) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else {
postfixString += chValue;
}
}
while (!opstack.empty()) {
String oper = String.valueOf(opstack.top());
if (!oper.equals(new String("("))) {
opstack.pop();
postfixString += oper;
}
}
String[] strValues = postfixString.split(",");
ArrayList<String> postfix = new ArrayList<String>(Arrays.asList(strValues));
return postfix;
}
整个class代码是：
package sr.stu;
import sr.cs.Stack;
import sr.stu.StackNode;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
* A program that converts an infix expression to postfix.<br>
* <br>
* Usage: java InToPost filename<br>
* <br>
* For example, prog1.in, containing infix expressions (one per line):<br>
* <br>
* A + B<br>
* A + B * C<br>
* A + B * C + D<br>
* ( A + B ) * C<br>
* ( A + B ) / ( C - D )<br>
* ( ( A + B ) * C - ( D - E ) )<br>
* <br>
* When run: java InToPost prog1.in:<br>
* <br>
* InToPost: converting expressions from infix to postfix...<br>
* [A, +, B]<br>
* [A, +, B, *, C]<br>
* [A, +, B, *, C, +, D]<br>
* [(, A, +, B, ), *, C]<br>
* [(, A, +, B, ), /, (, C, -, D, )]<br>
* [(, (, A, +, B, ), *, C, -, (, D, -, E, ), )]<br>
* InToPost: emitting postfix expressions...<br>
* A B +<br>
* A B C * +<br>
* A B C * + D +<br>
* A B + C *<br>
* A B + C D - /<br>
* A B + C * D E - -<br>
* <br>
*/
public class InToPost{
/** The add operator */
public final static String ADD = "+";
/** The subtract operator */
public final static String SUBTRACT = "-";
/** The multiply operator */
public final static String MULTIPLY = "*";
/** The divide operator */
public final static String DIVIDE = "/";
/** The open parentheses operator */
public final static String OPEN_PAREN = "(";
/** The close parentheses operator */
public final static String CLOSE_PAREN = ")";
/** The list of converted postfix expressions */
private List<List<String>> expressions;
/** The name of the infix source file */
private String srcFile;
/** A dictionary that maps operators (strings) to their precedence level
* (integer) from highest (3) to lowest (1):
* *, /: 3
* +, -: 2
* (: 1
*/
private Map<String, Integer> precedence;
/**
* Create a new IntoPost object.
* @param filename The name of the infix source file
*/
public InToPost(String filename) {
this.expressions = new LinkedList<>();
this.srcFile = filename;
/** populate the precedence map */
this.precedence = new HashMap<>();
this.precedence.put(MULTIPLY, 3);
this.precedence.put(DIVIDE, 3);
this.precedence.put(ADD, 2);
this.precedence.put(SUBTRACT, 2);
this.precedence.put(OPEN_PAREN, 1);
}
/**
* A private utility method that can be used by the private convert
* method when dealing with the precedence of math operators on
* the stack. Indicates whether the top token on stack has greater
* than or equal precedence than the current token. For example:
* greaterEqualPrecedence("+", "*") -> false
* greaterEqualPrecedence("*", "+") -> true
* greaterEqualPrecedence("+", "-") -> true
* greaterEqualPrecedence("(", "/") -> false
*
* @param token the current math token, e.g. "+"
* @param top the top token to compare to, e.g. "*"
* @return true if top has greater than or equal precedence than
* token, false otherwise
*/
private boolean greaterEqualPrecedence(String top, String token) {
return this.precedence.get(top) >= this.precedence.get(token);
}
/**
* A private helper conversion function that takes a list of tokens
* (strings) in infix form and converts them to a list of tokens
* (strings) in postfix form.
*
* For example:
* tokens = ["A", "+", "B"]
* postfix = ["A", "B", "+"]
*
* Note, this method must use either StackList<T> or StackNode<T>
* to represent the stack structure in the conversion algorithm.
*
* @param tokens the list of tokens (strings) in infix form
* @return a new list of tokens (strings) in postfix form
*/
private List<String> convert(List<String> tokens) {
// YOUR IMPLEMENTATION HERE
StackNode opstack = new StackNode();
//List<Object> postfix = new ArrayList<Object>();
//int sizeOfList=tokens.size();
String postfixString = " ";
for (int index = 0; index < tokens.size(); ++index) {
String chValue = tokens.get(index);
if (chValue == "(") {
opstack.push("(");
} else if (chValue == ")") {
String oper = String.valueOf(opstack.top());
while (!(oper.equals("(")) && !(opstack.empty())) {
postfixString += oper;
opstack.pop();
oper = String.valueOf(opstack.top());
}
opstack.pop();
} else if (chValue == "+" || chValue == "-") {
//Stack is empty
if (opstack.empty()) {
opstack.push(chValue);
//current Stack is not empty
} else {
String oper = String.valueOf(opstack.top());
while (!(opstack.empty() || oper.equals(new String("(")) || oper.equals(new String(")")))) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else if (chValue == "*" || chValue == "/") {
if (opstack.empty()) {
opstack.push(chValue);
} else {
String oper = String.valueOf(opstack.top());
while (!oper.equals(new String("+")) && !oper.equals(new String("-")) && !opstack.empty()) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else {
postfixString += chValue;
}
}
while (!opstack.empty()) {
String oper = String.valueOf(opstack.top());
if (!oper.equals(new String("("))) {
opstack.pop();
postfixString += oper;
}
}
String[] strValues = postfixString.split(",");
ArrayList<String> postfix = new ArrayList<String>(Arrays.asList(strValues));
return postfix;
}
/**
* The public conversion function that converts all infix expressions
* in the source file (one per line), into postfix expressions.
* @throws FileNotFoundException if the file is not found
*/
public void convert() throws FileNotFoundException {
Scanner in = new Scanner(new File(this.srcFile));
while (in.hasNext()) {
// convert the line into a list of strings, e.g.
// line = "A B +"
// tokens = ["A", "B", "+"]
List<String> tokens = Arrays.asList(in.nextLine().split(" "));
// if the line isn't empty, convert it to postfix and add it to
// the list of expressions
if (tokens.size() > 0) {
System.out.println(tokens);
this.expressions.add(convert(tokens));
}
}
}
/**
* Display the converted postfix expressions.
*/
public void emit() {
for (List<String> expression : this.expressions) {
for (String token : expression) {
System.out.print(token + " ");
}
System.out.println();
}
}
/**
* The main program takes the source file of infix expressions, converts
* them to postfix, and displays them.
* @param args command line arguments
* @throws FileNotFoundException if the source file is not found
*/
public static void main(String[] args) throws FileNotFoundException {
if (args.length != 1) {
System.out.println("Usage: java InToPost.py source-file.in");
return;
}
InToPost inToPost = new InToPost(args[0]);
System.out.println("InToPost: converting expressions from infix to postfix...");
inToPost.convert();
System.out.println("InToPost: emitting postfix expressions...");
inToPost.emit();
}
}
这是一种可能性。您可以分析此代码并找出您的代码中的错误。
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);
}
}
}
来源：http://www.tutorialspoint.com/javaexamples/data_intopost.htm
你可以查看我的代码。在这里，中缀到后缀的转换是按照运算符的优先级和结合性的所有规则执行的。
一些转换规则是：
- 在操作数到达时打印它们。
- 如果堆栈为空或顶部包含左括号，则将传入运算符压入堆栈。
- 如果传入符号是'('，将其压入堆栈。
- 如果传入的符号是')'弹出堆栈并打印运算符单元左'('遇到；弹出'('但不将其添加到结果。
- 如果传入符号的优先级高于堆栈顶部，则将其压入堆栈。
- 如果传入符号的优先级低于栈顶，弹出并打印 top.Then 测试传入运算符是否位于新的栈顶。
- 如果传入符号与栈顶具有相同的优先级，则使用关联性规则。
- 结合性规则，如果结合性为L-R，则出栈并打印栈顶，压入传入运算符
- 结合性规则，如果结合性是R-L，则将传入的运算符压入堆栈。
- 在表达式的末尾，弹出并打印堆栈的所有运算符。
更多信息请参考：Coding-Problems
package com.stack.problems;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class InfixToPostfixConversionUsingStack {
static int precedence(Character ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static boolean associativityForEqualPrecedence(char ch1, char ch2) {
/* Here, true represent L-R associativity and vice-versa.
* */
List<Character> charList = Arrays.asList('+', '-', '*', '/');
return charList.contains(ch1) || charList.contains(ch2); //Rule 8,9
}
private static String infixToPostfix(String exp) {
if (exp == null || exp.isEmpty())
return exp;
Stack<Character> stack = new Stack<>();
StringBuilder result = new StringBuilder();
for (int index = 0; index < exp.length(); index++) {
char ch = exp.charAt(index);
if (Character.isLetterOrDigit(ch)) {
result.append(ch); //Rule 1
} else if (ch == '(') { //Rule 3
stack.push(ch);
} else if (ch == ')') { //Rule 4
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
if (!stack.isEmpty())
stack.pop();
else { //For invalid expression...
System.out.println("Mismatched parenthesis....");
return null;
}
} else if (!stack.isEmpty()) {
if (precedence(ch) > precedence(stack.peek())) { //Rule 5
stack.push(ch);
} else if (precedence(ch) < precedence(stack.peek())) { //Rule 6
while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
result.append(stack.pop());
}
stack.push(ch);
} else { //Rule 7
//Here operators are having equal precedence therefore associativity rules are applied...
if (associativityForEqualPrecedence(ch, stack.peek())) {
result.append(stack.pop());
}
stack.push(ch);
}
} else if (stack.isEmpty() || stack.peek() == '(') { //Rule 2
stack.push(ch);
}
}
//For handling invalid expression...
if (!stack.isEmpty() && stack.search('(') != -1) {
System.out.println("Mismatched parenthesis...");
return null;
}
if (!stack.isEmpty()) { //Rule 10
while (!stack.isEmpty()) {
result.append(stack.pop());
}
}
return result.toString();
}
public static void main(String[] args) {
String[] exprArray = {
"K+L-M*N+(O^P)*W/U/V*T+Q^J^A",
"a+b*(c^d-e)^(f+g*h)-i",
"((a+b-c)*d^e^f)/g",
"1+2+3*5+(6+7)+8",
"((a-b)/c)",
"a*b-a*b+a*b",
"(a*b"};
for (int index = 0; index < exprArray.length; index++) {
System.out.println("Infix Expression: " + exprArray[index]);
System.out.println("Postfix Expression: " + infixToPostfix(exprArray[index]));
}
}
}
我有一个 java class 可以将中缀表达式转换为后缀。我设法使 class 运行 没有错误，但它没有给我正确的输出。输出的格式应该是 :
InToPost: converting expressions from infix to postfix...
[A, +, B]
[A, +, B, *, C]
[A, +, B, *, C, +, D]
[(, A, +, B, ), *, C]
[(, A, +, B, ), /, (, C, -, D, )]
[(, (, A, +, B, ), *, C, -, (, D, -, E, ), )]
InToPost: emitting postfix expressions...
A B +
A B C * +
A B C * + D +
A B + C *
A B + C D - /
A B + C * D E - -
但我的输出是：
InToPost: converting expressions from infix to postfix... [A, +, B]
[A, +, B, *, C]
[A, +, B, *, C, +, D]
[(, A, +, B, ), *, C]
[(, A, +, B, ), /, (, C, -, D, )]
[(, (, A, +, B, ), , C, -, (, D, -, E, ), )]
InToPost: emitting postfix expressions... A+B
A+BC
A+B*C+D
(A+B)*C
(A+B)/(C-D)
((A+B)*C-(D-E))
转换方法如下：
private List<String> convert(List<String> tokens) {
// YOUR IMPLEMENTATION HERE
StackNode opstack = new StackNode();
//List<Object> postfix = new ArrayList<Object>();
//int sizeOfList=tokens.size();
String postfixString = " ";
for (int index = 0; index < tokens.size(); ++index) {
String chValue = tokens.get(index);
if (chValue == "(") {
opstack.push("(");
} else if (chValue == ")") {
String oper = String.valueOf(opstack.top());
while (!(oper.equals("(")) && !(opstack.empty())) {
postfixString += oper;
opstack.pop();
oper = String.valueOf(opstack.top());
}
opstack.pop();
} else if (chValue == "+" || chValue == "-") {
//Stack is empty
if (opstack.empty()) {
opstack.push(chValue);
//current Stack is not empty
} else {
String oper = String.valueOf(opstack.top());
while (!(opstack.empty() || oper.equals(new String("(")) || oper.equals(new String(")")))) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else if (chValue == "*" || chValue == "/") {
if (opstack.empty()) {
opstack.push(chValue);
} else {
String oper = String.valueOf(opstack.top());
while (!oper.equals(new String("+")) && !oper.equals(new String("-")) && !opstack.empty()) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else {
postfixString += chValue;
}
}
while (!opstack.empty()) {
String oper = String.valueOf(opstack.top());
if (!oper.equals(new String("("))) {
opstack.pop();
postfixString += oper;
}
}
String[] strValues = postfixString.split(",");
ArrayList<String> postfix = new ArrayList<String>(Arrays.asList(strValues));
return postfix;
}
整个class代码是：
package sr.stu;
import sr.cs.Stack;
import sr.stu.StackNode;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
* A program that converts an infix expression to postfix.<br>
* <br>
* Usage: java InToPost filename<br>
* <br>
* For example, prog1.in, containing infix expressions (one per line):<br>
* <br>
* A + B<br>
* A + B * C<br>
* A + B * C + D<br>
* ( A + B ) * C<br>
* ( A + B ) / ( C - D )<br>
* ( ( A + B ) * C - ( D - E ) )<br>
* <br>
* When run: java InToPost prog1.in:<br>
* <br>
* InToPost: converting expressions from infix to postfix...<br>
* [A, +, B]<br>
* [A, +, B, *, C]<br>
* [A, +, B, *, C, +, D]<br>
* [(, A, +, B, ), *, C]<br>
* [(, A, +, B, ), /, (, C, -, D, )]<br>
* [(, (, A, +, B, ), *, C, -, (, D, -, E, ), )]<br>
* InToPost: emitting postfix expressions...<br>
* A B +<br>
* A B C * +<br>
* A B C * + D +<br>
* A B + C *<br>
* A B + C D - /<br>
* A B + C * D E - -<br>
* <br>
*/
public class InToPost{
/** The add operator */
public final static String ADD = "+";
/** The subtract operator */
public final static String SUBTRACT = "-";
/** The multiply operator */
public final static String MULTIPLY = "*";
/** The divide operator */
public final static String DIVIDE = "/";
/** The open parentheses operator */
public final static String OPEN_PAREN = "(";
/** The close parentheses operator */
public final static String CLOSE_PAREN = ")";
/** The list of converted postfix expressions */
private List<List<String>> expressions;
/** The name of the infix source file */
private String srcFile;
/** A dictionary that maps operators (strings) to their precedence level
* (integer) from highest (3) to lowest (1):
* *, /: 3
* +, -: 2
* (: 1
*/
private Map<String, Integer> precedence;
/**
* Create a new IntoPost object.
* @param filename The name of the infix source file
*/
public InToPost(String filename) {
this.expressions = new LinkedList<>();
this.srcFile = filename;
/** populate the precedence map */
this.precedence = new HashMap<>();
this.precedence.put(MULTIPLY, 3);
this.precedence.put(DIVIDE, 3);
this.precedence.put(ADD, 2);
this.precedence.put(SUBTRACT, 2);
this.precedence.put(OPEN_PAREN, 1);
}
/**
* A private utility method that can be used by the private convert
* method when dealing with the precedence of math operators on
* the stack. Indicates whether the top token on stack has greater
* than or equal precedence than the current token. For example:
* greaterEqualPrecedence("+", "*") -> false
* greaterEqualPrecedence("*", "+") -> true
* greaterEqualPrecedence("+", "-") -> true
* greaterEqualPrecedence("(", "/") -> false
*
* @param token the current math token, e.g. "+"
* @param top the top token to compare to, e.g. "*"
* @return true if top has greater than or equal precedence than
* token, false otherwise
*/
private boolean greaterEqualPrecedence(String top, String token) {
return this.precedence.get(top) >= this.precedence.get(token);
}
/**
* A private helper conversion function that takes a list of tokens
* (strings) in infix form and converts them to a list of tokens
* (strings) in postfix form.
*
* For example:
* tokens = ["A", "+", "B"]
* postfix = ["A", "B", "+"]
*
* Note, this method must use either StackList<T> or StackNode<T>
* to represent the stack structure in the conversion algorithm.
*
* @param tokens the list of tokens (strings) in infix form
* @return a new list of tokens (strings) in postfix form
*/
private List<String> convert(List<String> tokens) {
// YOUR IMPLEMENTATION HERE
StackNode opstack = new StackNode();
//List<Object> postfix = new ArrayList<Object>();
//int sizeOfList=tokens.size();
String postfixString = " ";
for (int index = 0; index < tokens.size(); ++index) {
String chValue = tokens.get(index);
if (chValue == "(") {
opstack.push("(");
} else if (chValue == ")") {
String oper = String.valueOf(opstack.top());
while (!(oper.equals("(")) && !(opstack.empty())) {
postfixString += oper;
opstack.pop();
oper = String.valueOf(opstack.top());
}
opstack.pop();
} else if (chValue == "+" || chValue == "-") {
//Stack is empty
if (opstack.empty()) {
opstack.push(chValue);
//current Stack is not empty
} else {
String oper = String.valueOf(opstack.top());
while (!(opstack.empty() || oper.equals(new String("(")) || oper.equals(new String(")")))) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else if (chValue == "*" || chValue == "/") {
if (opstack.empty()) {
opstack.push(chValue);
} else {
String oper = String.valueOf(opstack.top());
while (!oper.equals(new String("+")) && !oper.equals(new String("-")) && !opstack.empty()) {
opstack.pop();
postfixString += oper;
}
opstack.push(chValue);
}
} else {
postfixString += chValue;
}
}
while (!opstack.empty()) {
String oper = String.valueOf(opstack.top());
if (!oper.equals(new String("("))) {
opstack.pop();
postfixString += oper;
}
}
String[] strValues = postfixString.split(",");
ArrayList<String> postfix = new ArrayList<String>(Arrays.asList(strValues));
return postfix;
}
/**
* The public conversion function that converts all infix expressions
* in the source file (one per line), into postfix expressions.
* @throws FileNotFoundException if the file is not found
*/
public void convert() throws FileNotFoundException {
Scanner in = new Scanner(new File(this.srcFile));
while (in.hasNext()) {
// convert the line into a list of strings, e.g.
// line = "A B +"
// tokens = ["A", "B", "+"]
List<String> tokens = Arrays.asList(in.nextLine().split(" "));
// if the line isn't empty, convert it to postfix and add it to
// the list of expressions
if (tokens.size() > 0) {
System.out.println(tokens);
this.expressions.add(convert(tokens));
}
}
}
/**
* Display the converted postfix expressions.
*/
public void emit() {
for (List<String> expression : this.expressions) {
for (String token : expression) {
System.out.print(token + " ");
}
System.out.println();
}
}
/**
* The main program takes the source file of infix expressions, converts
* them to postfix, and displays them.
* @param args command line arguments
* @throws FileNotFoundException if the source file is not found
*/
public static void main(String[] args) throws FileNotFoundException {
if (args.length != 1) {
System.out.println("Usage: java InToPost.py source-file.in");
return;
}
InToPost inToPost = new InToPost(args[0]);
System.out.println("InToPost: converting expressions from infix to postfix...");
inToPost.convert();
System.out.println("InToPost: emitting postfix expressions...");
inToPost.emit();
}
}
这是一种可能性。您可以分析此代码并找出您的代码中的错误。
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);
}
}
}
来源：http://www.tutorialspoint.com/javaexamples/data_intopost.htm
你可以查看我的代码。在这里，中缀到后缀的转换是按照运算符的优先级和结合性的所有规则执行的。
一些转换规则是：
- 在操作数到达时打印它们。
- 如果堆栈为空或顶部包含左括号，则将传入运算符压入堆栈。
- 如果传入符号是'('，将其压入堆栈。
- 如果传入的符号是')'弹出堆栈并打印运算符单元左'('遇到；弹出'('但不将其添加到结果。
- 如果传入符号的优先级高于堆栈顶部，则将其压入堆栈。
- 如果传入符号的优先级低于栈顶，弹出并打印 top.Then 测试传入运算符是否位于新的栈顶。
- 如果传入符号与栈顶具有相同的优先级，则使用关联性规则。
- 结合性规则，如果结合性为L-R，则出栈并打印栈顶，压入传入运算符
- 结合性规则，如果结合性是R-L，则将传入的运算符压入堆栈。
- 在表达式的末尾，弹出并打印堆栈的所有运算符。
更多信息请参考：Coding-Problems
package com.stack.problems;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class InfixToPostfixConversionUsingStack {
static int precedence(Character ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static boolean associativityForEqualPrecedence(char ch1, char ch2) {
/* Here, true represent L-R associativity and vice-versa.
* */
List<Character> charList = Arrays.asList('+', '-', '*', '/');
return charList.contains(ch1) || charList.contains(ch2); //Rule 8,9
}
private static String infixToPostfix(String exp) {
if (exp == null || exp.isEmpty())
return exp;
Stack<Character> stack = new Stack<>();
StringBuilder result = new StringBuilder();
for (int index = 0; index < exp.length(); index++) {
char ch = exp.charAt(index);
if (Character.isLetterOrDigit(ch)) {
result.append(ch); //Rule 1
} else if (ch == '(') { //Rule 3
stack.push(ch);
} else if (ch == ')') { //Rule 4
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
if (!stack.isEmpty())
stack.pop();
else { //For invalid expression...
System.out.println("Mismatched parenthesis....");
return null;
}
} else if (!stack.isEmpty()) {
if (precedence(ch) > precedence(stack.peek())) { //Rule 5
stack.push(ch);
} else if (precedence(ch) < precedence(stack.peek())) { //Rule 6
while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
result.append(stack.pop());
}
stack.push(ch);
} else { //Rule 7
//Here operators are having equal precedence therefore associativity rules are applied...
if (associativityForEqualPrecedence(ch, stack.peek())) {
result.append(stack.pop());
}
stack.push(ch);
}
} else if (stack.isEmpty() || stack.peek() == '(') { //Rule 2
stack.push(ch);
}
}
//For handling invalid expression...
if (!stack.isEmpty() && stack.search('(') != -1) {
System.out.println("Mismatched parenthesis...");
return null;
}
if (!stack.isEmpty()) { //Rule 10
while (!stack.isEmpty()) {
result.append(stack.pop());
}
}
return result.toString();
}
public static void main(String[] args) {
String[] exprArray = {
"K+L-M*N+(O^P)*W/U/V*T+Q^J^A",
"a+b*(c^d-e)^(f+g*h)-i",
"((a+b-c)*d^e^f)/g",
"1+2+3*5+(6+7)+8",
"((a-b)/c)",
"a*b-a*b+a*b",
"(a*b"};
for (int index = 0; index < exprArray.length; index++) {
System.out.println("Infix Expression: " + exprArray[index]);
System.out.println("Postfix Expression: " + infixToPostfix(exprArray[index]));
}
}
}