Admin: 1 версия

2010-06-01T07:26:39Z

1 версия

в 18:01, 31 мая 2010

2010-05-31T18:01:50Z

Новая страница

== Converts infix arithmetic expressions to postfix ==



<source lang="java">
import java.io.IOException;
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; // (precedence 1)
case "*": // it"s * or /
case "/":
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case "(": // it"s a left paren
theStack.push(ch); // push it
break;
case ")": // it"s a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();
}
System.out.println(output);
return output; // return postfix
}
public void gotOper(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == "(") {
theStack.push(opTop);
break;
}// it"s an operator
else {// precedence of new op
int prec2;
if (opTop == "+" || opTop == "-")
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) // if prec of new op less
{ // than prec of old
theStack.push(opTop); // save newly-popped op
break;
} else
// prec of new not less
output = output + opTop; // than prec of old
}
}
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 = "1+2*4/5-7+3/6";
String output;
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans();
System.out.println("Postfix is " + output + "\n");
}
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);
}
}
}

</source>



== Parse postfix arithmetic expressions ==



<source lang="java">
import java.io.IOException;
public class ParsePost {
private Stack theStack;
private String input;
public ParsePost(String s) {
input = s;
}
public int doParse() {
theStack = new Stack(20);
char ch;
int j;
int num1, num2, interAns;
for (j = 0; j < input.length(); j++) {
ch = input.charAt(j);
theStack.displayStack("" + ch + " ");
if (ch >= "0" && ch <= "9") // if a number push it
theStack.push((int) (ch - "0"));
else // it"s an operator
{
num2 = theStack.pop();
num1 = theStack.pop();
switch (ch) {
case "+":
interAns = num1 + num2;
break;
case "-":
interAns = num1 - num2;
break;
case "*":
interAns = num1 * num2;
break;
case "/":
interAns = num1 / num2;
break;
default:
interAns = 0;
}
theStack.push(interAns);
}
}
interAns = theStack.pop();
return interAns;
}
public static void main(String[] args) throws IOException {
String input = "1-2+3*4+5/6-7+8*9";
int output;
ParsePost aParser = new ParsePost(input);
output = aParser.doParse();
System.out.println("Evaluates to " + output);
}
class Stack {
private int maxSize;

private int[] stackArray;

private int top;

public Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}

public void push(int j) {
stackArray[++top] = j;
}

public int pop() {
return stackArray[top--];
}

public int peek() {
return stackArray[top];
}

public boolean isEmpty() {
return (top == -1);
}

public boolean isFull() {
return (top == maxSize - 1);
}

public int size() {
return top + 1;
}

public int peekN(int n) {
return stackArray[n];
}

public void displayStack(String s) {
System.out.print(s);
System.out.print("Stack (bottom>top): ");
for (int j = 0; j < size(); j++) {
System.out.print(peekN(j));
System.out.print(" ");
}
System.out.println("");
}
}
}

</source>

← Предыдущая	Версия 07:26, 1 июня 2010
(нет различий)

Java/Collections Data Structure/Infix Postfix - История изменений

Admin: 1 версия

в 18:01, 31 мая 2010