assignment is to write a program that converts an expression from infix notation
ID: 3546904 • Letter: A
Question
assignment is to write a program that converts an expression from infix notation to either prefix or postfix notation, the form chosen by the program's user.
The infix expressions that your program needs to handle involve (decimal) integer constants, such as 3 and 72, single-letter variable names, binary operators +, -, * and /, and parentheses. Operators + and- have the same precedence, and are performed from right to left. Operators * and / have the same precedence, which is higher than the precedence of + and -, and they are also done from right to left. Spaces in the input are optional, and are ignored. The output is printed with one space between each part (including operators).
The input begins either with prefix or postfix, indicating the desired output form. For example, if the input is
then the program should print
The string to be converted should be on the command line. Your program will be called Convert.java. Command
should print
The command line can have several parts, separated by spaces, and your program needs to consider them all. For example,
should also print
The command line arguments are given to the main program as the array parameter, args. For example, command
will call main with args[0] = "prefix", args[1] = "2", args[2] = "+" and args[3] = "3*4". The command is normally broken at white space. Quotes override that. So command
calls main with args[0] = "postfix 2+3*45".
This program always writes the result on the standard output (System.out).
http://www.cs.ecu.edu/karl/3310/spr08/parser/large1.htm
Explanation / Answer
//Code : javac filename.java and run with java Compute_Expression postfix a+b*c
import java.io.*;
class Stack
{
private char[] a;
private int top,m;
public Stack(int max)
{
m=max;
a=new char[m];
top=-1;
}
public void push(char key)
{
a[++top]=key;
}
public char pop()
{
return(a[top--]);
}
public char peek()
{
return(a[top]);
}
public boolean isEmpty()
{
return (top==-1);
}
}
class Evaluation
{
private Stack s;
private String input;
private String output="";
public Evaluation(String str)
{
input=str;
s=new Stack(str.length());
}
public String inToPre()
{
for(int i=input.length()-1;i>=0;i--)
{
char ch=input.charAt(i);
switch(ch)
{
case '+':
case '-':gotOperator(ch,1,')');
break;
case '*':
case '/':gotOperator(ch,2,')');
break;
case ')':s.push(ch);
break;
case '(':gotParenthesis(')');
break;
default:output=ch+output;
}
}
while(!s.isEmpty())
output=s.pop()+output;
return output;
}
public String inToPost()
{
for(int i=0;i<input.length();i++)
{
char ch=input.charAt(i);
switch(ch)
{
case '+':
case '-':gotOperator(ch,1,'(');
break;
case '*':
case '/':gotOperator(ch,2,'(');
break;
case '(':s.push(ch);
break;
case ')':gotParenthesis('(');
break;
default:output=output+ch;
}
}
while(!s.isEmpty())
output=output+s.pop();
return output;
}
public String preToPost()
{
Stack f=new Stack(input.length());
for(int i=0;i<input.length();i++)
{
char ch=input.charAt(i);
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
s.push(ch);
f.push('0');
}
else
{
output=output+ch;
while(f.peek()=='1')
{
output=output+s.pop();
f.pop();
if(f.isEmpty())
break;
}
if(!f.isEmpty())
f.pop();
f.push('1');
}
}
return output;
}
private void gotOperator(char opThis,int prec1,char x)
{
while(!s.isEmpty())
{
char opTop=s.pop();
if(opTop==x)
{
s.push(opTop);
break;
}
else
{
int prec2;
if(opTop=='+'||opTop=='-')
prec2=1;
else
prec2=2;
if(prec2<prec1&&x=='(')
{
s.push(opTop);
break;
}
else if(prec2<=prec1&&x==')')
{
s.push(opTop);
break;
}
else
{
if(x==')')
output=opTop+output;
else
output=output+opTop;
}
}
}
s.push(opThis);
}
private void gotParenthesis(char x)
{
while(!s.isEmpty())
{
char ch=s.pop();
if(ch==x)
break;
else
{
if(x==')')
output=ch+output;
else
output=output+ch;
}
}
}
}
class Compute_Expression{
public static void main(String args[]){
Evaluation inf = new Evaluation(args[1]);
if(args[0].equals("prefix")){
System.out.println(inf.inToPre());
}
if(args[0].equals("postfix")){
System.out.println(inf.inToPost());
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.