题
I have been attempting to write a code that converts Prefix expressions to Postfix expressions.
So far here's what I have made (note that I am new and hence may not be efficient!)
https://stackoverflow.com/questions/18508456
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian/***************************************************
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();
}
}
As I have already commented in the code, my code fails to realize the precedence in the case of prefix expressions.
For example:
Infix : a + (b*c)
Prefix : +a*bc
Postfix : abc*+ //Expected output
Output I get : ab*c+
Is something wrong in the logic I am using or is there something I need to add? Can you please suggest some method by means of which my code can work properly? If anybody can help I will be grateful.
NB: Our professor has advised us to write our own stack class and code. Please also note that this is kind of a homework assignment.
Thanks in advance.
Edit: In order to make sure that my STACK works fine I wrote the following piece of code and it works perfectly alright.
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);
}
}
EDIT I finally managed to create a program that works perfectly fine.
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();
}
}
解决方案
The code you have written only does the job of shifting the operators from left to right. A nudge in the right direction :
Insert a condition to check for operators between symbols in the prefix string and solve them first!
This might solve your problem.
