我一直在尝试编写将前缀表达式转换为后缀表达式的代码。
到目前为止，这是我所做的（请注意，我是新手，因此可能效率不高！）
/***************************************************
NOTE: This code fails to realise the precedence
of parentheses and $ (exponential) expressions
****************************************************/
import java.util.Scanner;
class Stack{
//Private Declarations
private int top;
private String a[] = new String [100];
//Public Declarations
public Stack(){
top = -1;
a[0] = "\0";
}
public void push(String x){
if (top != 99){
a[++top] = x;
}
else{
System.out.println("Stack overflow");
}
};
public String pop(){
if (top == -1){
System.out.println("\nStack empty!");
return "\n";
}
else{
return a[top--];
}
};
public int ret_top(){
return top;
};
}
public class Prefix2Postfix {
public static void main(String[] args) {
//Declaration
Scanner in = new Scanner (System.in);
Stack op = new Stack ();
Stack sym = new Stack ();
char ch;
int i;
String exp, str, str1, str2, str3;
//Taking input from the user
System.out.println("Enter the prefix expression : ");
exp = in.next();
for (i=0; i<exp.length(); i++){
ch = exp.charAt(i);
if((ch == '+')
||(ch == '-')
||(ch == '*')
||(ch == '/')
||(ch == '$')){
str = Character.toString(ch);
op.push(str);
}
else{
str = Character.toString(ch);
sym.push(str);
if (sym.ret_top() == 1){
str1 = sym.pop();
str2 = sym.pop();
str3 = op.pop();
str1 = str2.concat(str1);
str1 = str1.concat(str3);
sym.push(str1);
}
}
}
//Output
str = sym.pop();
System.out.println("After conversion to postfix" + ": " + str);
in.close();
}
}
正如我已经在代码中评论的那样，我的代码在前缀表达式的情况下无法实现优先级。
例如：
Infix : a + (b*c)
Prefix : +a*bc
Postfix : abc*+ //Expected output
Output I get : ab*c+
我使用的逻辑有问题还是需要添加什么？您能否建议一些我的代码可以正常工作的方法？如果有人可以提供帮助，我将不胜感激。
注意：我们的教授建议我们编写自己的堆栈类和代码。另请注意，这是一种家庭作业。
提前致谢。
编辑： 为了确保我的堆栈工作正常，我编写了以下代码，它工作得很好。
import java.util.Scanner;
class STACK {
//Private Declarations
private int top;
private int elem[] = new int [100];
//Public Declarations
public STACK (){
top = -1;
elem[0] = 0;
}
public void push(int x){
if (top != 99){
elem[++top] = x;
}
else{
System.out.println("Stack overflow");
}
};
public int pop(){
if (top == -1){
System.out.println("Stack empty!");
return 0;
}
else{
return elem[top--];
}
};
}
public class StackPushPop {
public static void main(String[] args) {
STACK s = new STACK();
Scanner in = new Scanner (System.in);
int choice, x;
do{
System.out.println("Menu Options :");
System.out.println("1 -> Push an element");
System.out.println("2 -> Pop an element");
System.out.println("3 -> Empty complete stack");
System.out.println("Any other input for exit");
System.out.println("Your choice : ");
choice = in.nextInt();
switch(choice){
case 1:
System.out.println("\nEnter element : ");
x = in.nextInt();
s.push(x);
break;
case 2:
System.out.print("\nPopping element : ");
x = s.pop();
if (x != 0){
System.out.println(x);
}
break;
case 3:
System.out.println("\nEmptying stack!");
x = 1;
while (x!= 0){
x = s.pop();
if(x != 0){
System.out.print(x + " ");
}
}
break;
default:
choice = 0;
}
}while (choice != 0);
}
}
编辑 我终于设法创建了一个运行良好的程序。
import java.util.Scanner;
class STACK{
private int top, MAX;
private String a[] = new String [1000];
public STACK(){
top = -1;
MAX = 1000;
a[0] = "";
}
public void push(String x){
if (top <= MAX-1){
a[++top] = x;
}
else{
System.out.println("Stack overflow");
}
};
public String pop(){
if (top == -1){
System.out.println("\nStack empty!");
return "\n";
}
else{
return a[top--];
}
};
public int getTop(){
return top;
};
}
public class Prefix2Postfix_STACK{
static boolean isOperator (char ch){
switch (ch){
case '+':
case '-':
case '*':
case '/':
case '$':
return true;
default :
return false;
}
}
public static void main(String[] args) {
//declarations
Scanner in = new Scanner (System.in);
String exp;
int i;
STACK s = new STACK ();
String exp_str[] = new String[100];
String postfix_exp = "\n";
//input
System.out.println("Enter prefix expression (No spaces or brackets) : ");
exp = in.next();
//create a string array of all characters but in reverse
for(i=0; i<=exp.length()-1; i++){
exp_str[exp.length()-1-i]=Character.toString(exp.charAt(i));
}
//computing postfix:
i=0;
do{
if (!isOperator(exp_str[i].charAt(0)))
s.push(exp_str[i]);
else{
String str1 = s.pop();
String str2 = s.pop();
str1 = str1 + str2 + exp_str[i];
postfix_exp = str1;
s.push(str1);
}
i++;
}while(s.getTop()>=0 && i!=exp.length());
//Output
System.out.println("After converting to postfix : " + postfix_exp);
in.close();
}
}