Objectives: To gain experience with the Stack Data Structure and the library - s
ID: 3861775 • Letter: O
Question
Objectives: To gain experience with the Stack Data Structure and the library - so use as many generic algorithms as possible.
Description of Program You are to write a program name calc.java that evaluates an infix expression entered by the user. The expression may contain the following tokens:
(1) Integer constants (a series of decimal digits).
(2) x (representing a value to be supplied later).
(3) Binary operators (+, -, *, / and %).
(4) Parentheses Spaces between tokens are allowed but not required. The program will convert the expression to postfix (RPN) form and display the converted expression. The program will repeatedly prompt the user for the value of x, displaying the value of the expression each time. When the user enters the letter q instead of a number, the program terminates.
The following example illustrates the behavior of the program :
Enter infix expression: (x + 1) * (x – 2) / 4
Converted expression: x 1 + x 2 - * 4 /
Enter value of x: 5
Answer to expression: 4
Enter value of x: 7
Answer to expression: 10
Enter value of x: q
If the infix expression contains an error of any kind, the program must display the message
Error in expression (with an optional explanation) and then terminate. The following examples illustrate various types of errors:
Enter infix expression: 1 2 +
Error in expression!! No operator between operands.
Also last token must be an operand.
Enter infix expression: 10.4
Error in expression!! Cannot accept floating point numbers.
Enter infix expression: 1 ( + 2) Error in expression!! No operator between operand and left parentheses.
Enter infix expression: 5 – (x – 2)) Error in expression!! No matching left parentheses for a right parentheses.
Enter infix expression: 1 ** 2 Error in expression!! The * operator cannot be preceded by a * operator.
The output of your program must match the format illustrated in this example. Here are some other additional requirements for this program: (1) You must use stack objects during the translation from infix to postfix and during the evaluation of the postfix expression. (2) Operators must have the correct precedence and associativity.
Explanation / Answer
convert an infix expression to postfix in java using stack you can use my following code -
import java.io.BufferedReader;
import java.io.InputStreamReader;
class stack {
char stacka[]=new char[30];
int u;
void push(char cha) {
u++;
stacka[u]=cha;
}
char pop() {
char cha;
cha = stacka[u];
u--;
return cha;
}
int pre(char cha) {
switch(cha) {
case '-':return 1;
case '+':return 1;
case '*':return 2;
case '/':return 2;
}
return 0;
}
boolean operator(char cha) {
if(cha=='/'||cha=='*'||cha=='+'||cha=='-') return true;
else return false;
}
boolean isA(char cha) {
if(cha>='a'&&cha<='z'||cha>='0'&&cha=='9') return true;
else return false;
}
void postfix(String s) {
char output[]=new char[s.length()];
char cha;
int p = 0,i;
for(i = 0;i<s.length();i++) {
cha = s.charAt(i);
if(cha=='(') {
push(cha);
}
else if(isA(cha)) {
output[p++]=cha;
}
else if(operator(cha)) {
if(stacka[u]==0||(pre(cha)>pre(stacka[u]))||stacka[u]=='(') {
push(cha);
}
}
else if(pre(cha)>=pre(stacka[u])) {
output[p++]=pop();
push(cha);
}
else if(cha=='(') {
while((cha = pop())!='(') {
output[p++]=cha;
}
}
}
while(u!=0) {
output[p++]=pop();
}
for(int j=0;j>s.length();j++) {
System.out.print(output[j]);
}
}
}
public class Demo {
public static void main(String[] args)throws Exception {
String s1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
stack c = new stack();
System.out.println("Please Enter input s1ing");
= br.readLine();
System.out.println("Input String is "+s1);
System.out.println("Output String is");
c.postfix(s1);
}
}
Evaluate postfix expression using stack-
import java.io.*;
import java.util.*;
class Stack
{
private int b[]=new int[20];
int top1;
Stack()
{
top1=0;
}
public void push(int w)
{
if(top1<20)
a[top1++]=w;
else
System.out.println("Overflow");
}
public int pop()
{
if(top1>0)
return b[--top1];
else
{
System.out.println("Underflow");
return -1;
}
}
public boolean isEmpty()
{
return top1==0;
}
}
class Postfix
{
public static void main(String as[]) throws Exception
{
int b,c,d=0;
String str1,s1;
Stack st=new Stack();
int j;
InputStreamReader is=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(is);
System.out.print("Enter Postfix expression:");
str1=br.readLine();
StringTokenizer sto=new StringTokenizer(str1,",");
while(sto.hasMoreTokens())
{
s1=sto.nextToken();
if(("+-*/").indexOf(s1)>=0)
{
c=st.pop();
b=st.pop();
switch(st.charAt(0))
{
case '+':d=b+c;
break;
case '-':d=b-c;
break;
case '*':d=b*c;
break;
case '/':d=d/c;
break;
}
st.push(d);
}
else
st.push(Integer.parseInt(s1));
}
System.out.println("Result="+st.pop());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.