Arithmetic%20Expressions%3A%20infix%20and%20postfix%20forms%0AThe%20standard%20m

Question

Arithmetic%20Expressions%3A%20infix%20and%20postfix%20forms%0AThe%20standard%20mathematical%20way%20of%20writing%20arithmetic%20expressions%20uses%20what%20is%20called%20infix%20notation%20where%20the%20operator%20occurs%20in%20between%20the%20two%20operands.%20%20For%20example%2C%2031%20-%20(2%20%2B%203)%20*5.%20%20To%20avoid%20the%20ambiguity%20of%20the%20order%20in%20which%20we%20should%20apply%20the%20operations%2C%20we%20use%20precedence%20rules%20(e.g.%20*%20before%20%2B)%20and%20parenthesis.%20%20An%20alternative%20form%20is%20to%20use%20postfix%20notation%20where%20the%20operator%20occurs%20after%20its%20operands.%20%20The%20equivalent%20postfix%20form%20of%20the%20preceding%20example%20is%20%E2%80%9C31%202%203%20%2B%205%20*%20%E2%80%93%E2%80%9C.%20%20This%20looks%20strange%20at%20first%20but%20it%20does%20have%20some%20advantages.%0AFirst%2C%20it%20easier%20for%20a%20computer%20to%20evaluate%20expressions%20in%20this%20form.%20%20You%20need%20only%20a%20stack%20and%20a%20single%20left%20to%20right%20pass%20of%20the%20expression%20(using%20infix%20notation%2C%20you%20constantly%20need%20to%20move%20back%20and%20forth%20searching%20for%20the%20next%20operation%20to%20perform).%20%20Scanning%20the%20postfix%20expression%20we%20do%20the%20following.%20%20Stack%20all%20operands.%20%20When%20we%20encounter%20an%20operator%2C%20we%20perform%20that%20operation%20on%20the%20preceding%20two%20operands%20and%20replace%20the%20subexpression%20with%20the%20result.%20%20So%20scanning%20our%20example%2C%20we%20get%2031%202%203%20%2B.%20%20Now%20we%20perform%202%2B3%20obtaining%20%E2%80%9C%2031%205%E2%80%9D.%20Continuing%20we%20get%2031%205%205%20*.%20%20We%20multiply%20the%20last%20two%20operands%20obtaining%20%E2%80%9C31%2025%E2%80%9D.%20%20Then%20we%20scan%20the%20final%20minus%20symbol%2C%20perform%2031%20%E2%80%93%2025%20obtaining%20the%20answer%20of%206.%20%20You%20can%20easily%20evaluate%20the%20infix%20form%20to%20verify%20that%20this%20is%20indeed%20the%20correct%20answer.%0AA%20second%20advantage%20of%20postfix%20form%20is%20that%20there%20is%20no%20need%20for%20parenthesis%2C%20precedence%20rules%2C%20nor%20associativity%20rules%20(e.g.%20multiplication%20and%20division%20associates%20left-to-right%20while%20exponentiation%20associates%20right-to-left).%20%20I.e.%20the%20form%20is%20simpler%20and%20hence%20easier%20to%20learn.%0A%0AThe%20assignment%0AYour%20assignment%20is%20to%20write%20a%20Java%20program%20that%20accepts%20input%20from%20a%20file%20where%20each%20line%20is%20a%20single%20arithmetic%20expression%20in%20infix%20form%2C%20converts%20each%20expression%20into%20its%20equivalent%20postfix%20form%2C%20and%20outputs%20the%20resulting%20postfix%20expression%20to%20the%20console.%20%20The%20operands%20will%20be%20variables%20(Strings)%20and%20the%20operators%20will%20be%20restricted%20to%20(%2C%20)%2C%20%2B%2C%20-%2C%20*%2C%20and%20%2F.%20%20The%20operators%20need%20to%20be%20assigned%20precedence%20values.%20The%20operators%20*%20and%20%2F%20have%20the%20highest%20precedence%2C%20the%20operators%20%2B%20and%20-%20have%20the%20next%20lowest%20precedence%2C%20and%20(%20has%20the%20lowest%20precedence%20of%20all%20--%20due%20to%20the%20algorithm%2C%20you%20don%E2%80%99t%20need%20to%20worry%20about%20the%20precedence%20of%20the%20right%20parenthesis).%20%20You%20can%20assign%20the%20operators%20the%20precedences%201%2C%202%2C%20and%203%20for%20example.%20%20You%20will%20need%20an%20initially%20empty%20operator%20stack.%20%20The%20algorithm%20is%20as%20follows.%20%20Scan%20the%20expression%20from%20left%20to%20right.%20%20If%20the%20next%20symbol%20is%20a%0A%0A%E2%80%A2%09Operand%3A%20print%20it%20out.%0A%E2%80%A2%09Left%20parenthesis%3A%20then%20push%20it%20onto%20the%20operator%20stack.%0A%E2%80%A2%09Right%20parenthesis%3A%20repeatedly%20pop%20and%20print%20the%20top%20stack%20operator%20until%20you%20pop%20a%20(matching)%20left%20parenthesis.%0A%E2%80%A2%09Regular%20operator%3A%20pop%20and%20print%20the%20top%20stack%20symbol%20until%20the%20top%20stack%20symbol%20has%20a%20lower%20precedence%20or%20until%20the%20stack%20is%20empty.%20Then%20push%20the%20operator%20onto%20the%20stack.%0AWhen%20you%20reach%20the%20end%20of%20the%20input%2C%20pop%20and%20print%20any%20remaining%20operators%20on%20the%20stack.%20%20The%20input%20filename%20is%20to%20be%20entered%20by%20the%20user%20(your%20code%20should%20check%20to%20make%20sure%20the%20file%20really%20exists%20--%20throw%20an%20exception%20if%20there%20is%20a%20problem%20reading%20the%20input%20file).%20%20You%20may%20assume%20that%20each%20input%20line%20is%20a%20valid%20infix%20expression.%0A%0ASubmission%0ASubmit%20your%20Java%20program%20in%20the%20assignment%20area.%0AFor%20all%20programs%20submitted%20as%20assignments%2C%20please%20include%20a%20package%20statement%20at%20the%20top%20of%20each%20.java%20file.%20%20The%20package%20name%20must%20be%20your%20last%20name%20in%20lowercase%20letter.%20%20I%20can%20compile%20and%20run%20a%20batch%20of%20Java%20programs%20a%20lot%20more%20quickly%20in%20another%20environment%20without%20an%20IDE.%20%20%20When%20running%20a%20program%20outside%20of%20an%20IDE%2C%20the%20package%20statement%20is%20necessary%3B%20the%20program%20will%20not%20run%20correctly%20without%20it.%20%20If%20you%20do%20not%20include%20the%20package%20statement%2C%20then%20it%20won't%20work%20when%20I%20try%20to%20compile%20and%20run%20your%20program.%20%20Then%20I%20have%20to%20figure%20out%20what%20is%20wrong%2C%20add%20the%20package%20statement%20to%20each%20of%20your%20source%20files%2C%20and%20recompile%20and%20rerun%20your%20program.%20%20Doing%20this%20several%20times%20is%20an%20annoying%20time%20waster%20that%20could%20be%20avoided%20simply%20by%20doing%20things%20the%20way%20they%20are%20supposed%20to%20be%20done%3B%20i.e.%20by%20including%20the%20package%20statement%20in%20each%20file.%0A%0ANote%3A%20postfix%20notation%20is%20sometimes%20called%20RPN%20(Reverse%20Polish%20Notation)%20after%20the%20Polish%20logician%20Jan%20Lukasiewicz%20who%20invented%20a%20prefix%20notation%20which%20has%20some%20advantages%20when%20working%20in%20logic.%20%20The%20reason%20for%20naming%20it%20after%20his%20nationality%20and%20not%20his%20name%20is%20due%20to%20the%20difficulty%20and%20confusion%20of%20pronouncing%20his%20name.%20%20Lukasiewicz%20is%20really%20an%20Anglicization.%20%20In%20polish%2C%20his%20name%20is%20%20jan%20wuka%3F%3F%3Fv%3Fit%3F.%0A%0ASample%20Stack%20Array%20code%3A%0Apublic%20class%20Stack%0A%20%20%20%7B%0A%20%20%20private%20char%20%5B%5D%20item%3B%20%20%20%20%20%20%2F%2F%20stack%20array%0A%20%20%20private%20int%20top%3B%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20index%20of%20the%20top%20element%0A%20%20%20private%20static%20final%20int%20DEFAULT_CAPACITY%20%3D%2016%3B%0A%0A%20%20%20Stack()%20%7B%20this(%20DEFAULT_CAPACITY%20)%3B%20%7D%0A%0A%20%20%20Stack(%20int%20capacity%20)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20item%20%3D%20new%20char%5B%20capacity%20%5D%3B%0A%20%20%20%20%20%20top%20%3D%20-1%3B%0A%20%20%20%20%20%20%7D%0A%0A%20%20%20public%20void%20push(%20char%20e%20)%20%7B%20item%5B%2B%2Btop%5D%20%3D%20e%3B%20%7D%0A%20%20%20public%20char%20pop()%20%20%20%20%20%20%20%20%20%20%7B%20return%20item%5Btop--%5D%3B%20%7D%0A%20%20%20public%20char%20peek()%20%20%20%20%20%20%20%20%20%7B%20return%20item%5Btop%5D%3B%20%7D%0A%20%20%20public%20boolean%20isEmpty()%20%20%20%7B%20return%20top%20%3D%3D%20-1%3B%20%7D%0A%20%20%20%7D%0A%0AText%20file%20contents%3A%0A4%2B5*2%0A(4%2B5)*2%0A1%2B2%2B3%2B4%2B5%0A1%2B(2%2B3)%2B(4%2B5)%0A3%2B4*5%2F6%0A(300%2B23)*(43-21)%2F(84%2B7)%0A(4%2B8)*(6-5)%2F((3-2)*(2%2B2))

Explanation / Answer

import java.io.IOException;

import java.io.*;

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;

String s: args;

try{

//Create object of FileReader

FileReader inputFile = new FileReader(s);

//Instantiate the BufferedReader Class

BufferedReader bufferReader = new BufferedReader(inputFile);

//Variable to hold the one line data

  

input = bufferReader.readLine();   

  

  

//Close the buffer reader

bufferReader.close();

}catch(Exception e){

System.out.println("Error while reading file line by line:"

+ e.getMessage());

}

String output;

InToPost theTrans = new InToPost(input);

output = theTrans.doTrans();

System.out.println("Postfix is " + output + ' ');

}

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);

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.