[About RPN] CS 1723 -- Translate Arithmetic Expression to RPN
CS 1723 -- Translate Arithmetic Expression to RPN
Here is a translator to RPN that uses the Java Stack class. This program also uses two other classes: Eval and GetNext that are listed here.
// Trans: translate input arith expr to RPN string
// Rules for each input char
// (go on to next input char unless otherwise stated)
// Fetch next char, call it ch
// 1. if ch is an operand, move it to output.
// From now on ch is an operator or '(' or ')'.
// 2. if stack is empty, add ch to stack.
// 3. if ch is '(', add ch to stack.
// From now on, stack is not empty. Use top for its top char.
// 4. if ch is ')', remove chars from stack and output down
// to '(' on stack, which is thrown away.
// 5. if top is '(', add ch to stack.
// From now on, both ch and top are regular operators.
// 6. if prec(ch) > prec(top), add ch to stack.
// 7. if prec(ch) < prec(top), move top to output, and
// DO NOT MOVE ON TO NEXT INPUT CHAR.
// 8. if prec(ch) == prec(top) and left-to-right associativity,
// move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
// 9. if prec(ch) == prec(top) and right-to-left associativity,
// add top to stack.
// 10. at end, move everything on stack to output.
import java.util.*;
public class Trans {
Stack stack; // java library stack of objects
public Trans() {
stack = new Stack();
}
// translate: an arith expr to RPN
public String translate(String s) {
double op1 = 0.0, op2 = 0.0, res = 0.0; // = 0.0, for compiler
String outStr = ""; // output string
char ch, top;
int i = 0; // index in input string
while (i < s.length()) {
boolean moveOn = true;
ch = s.charAt(i); // before Rule 1
if (Character.isDigit(ch) ) // Rule 1: digit to output
outStr += ch;
else if (stack.empty() || ch == '(') // Rules 2 and 3
stack.push(new Character(ch));
else { // stack is not empty
top = ((Character)(stack.peek())).charValue(); // before Rule 4
if (ch == ')') // Rule 4
while (true) {
if ((top=((Character)(stack.pop())).charValue()) == '(')
break; // normal termination
outStr += top;
if (stack.empty()) error(1);
}
else if (top == '(') // Rule 5
stack.push(new Character(ch));
else if (prec(ch) > prec(top) || (prec(ch) == prec(top) &&
assoc(ch) == 'r') ) // Rules 6 and 9
stack.push(new Character(ch));
else if (prec(ch) < prec(top) || (prec(ch) == prec(top) &&
assoc(ch) == 'l') ) { // Rules 7 and 8
outStr += top;
stack.pop();
moveOn = false;
}
}
if (moveOn) i++;
} // while
while (!stack.empty()) // Rule 10
outStr += ((Character)(stack.pop())).charValue();
return outStr;
}
// prec: return int precedence of operators
private int prec(char ch) {
switch (ch) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return -1;
}
}
// assoc: return 'l' for left-to-right, and 'r' for right-to-left
private char assoc(char ch) {
switch (ch) {
case '+': case '-': case '*': case '/': return 'l';
case '^': return 'r';
default: return '?';
}
}
// error: in case of an error
private void error(int num) {
System.out.println("Error number: " + num);
System.exit(0);
}
public static void main(String[] args) {
GetNext getNext = new GetNext(); // input class
Trans trans = new Trans(); // new translater
Eval eval = new Eval(); // new evaluator
while (true) { // read and translate indefinitely
String s = getNext.getNextString(); // fetch string
System.out.println("Input: " + s);
String resStr = trans.translate(s); // produce RPN
System.out.println("RPN string: " + resStr); // print RPN
double res = eval.evaluateRPN(resStr);
System.out.println("Value: " + res); // print value
}
}
}
Sample run. Here each translation to RPN is carried out, and then the evaluator from RPN evaluator is called to calculate a final value. % java Trans
2+3*4
Input: 2+3*4
RPN string: 234*+
Value: 14.0
2*3+4
Input: 2*3+4
RPN string: 23*4+
Value: 10.0
2^3^4
Input: 2^3^4
RPN string: 234^^
Value: 2.4178516392292583E24
2*(3+4)
Input: 2*(3+4)
RPN string: 234+*
Value: 14.0
2+(3*4)
Input: 2+(3*4)
RPN string: 234*+
Value: 14.0
((2)+(((3))))*((((4))))
Input: ((2)+(((3))))*((((4))))
RPN string: 23+4*
Value: 20.0
2+3*4^5*6+7
Input: 2+3*4^5*6+7
RPN string: 2345^*6*+7+
Value: 18441.0
2^3*4+5*6^7
Input: 2^3*4+5*6^7
RPN string: 23^4*567^*+
Value: 1399712.0
2-3-4
Input: 2-3-4
RPN string: 23-4-
Value: -5.0
2/3/4
Input: 2/3/4
RPN string: 23/4/
Value: 0.16666666666666666
2+3*4^5
Input: 2+3*4^5
RPN string: 2345^*+
Value: 3074.0
2^3*4+5
Input: 2^3*4+5
RPN string: 23^4*5+
Value: 37.0
2+3*4^5+6
Input: 2+3*4^5+6
RPN string: 2345^*+6+
Value: 3080.0
1+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2))))))))))))))))))))
Input: 1+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2))))))))))))))))))))
RPN string: 11212121212121212121212121212121212121212/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value: 1.414213562373095
(Note:sqrt(2) = 1.414213562373095048801688724209...)
2+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(2*5+1/(1+1/(1+1/(2*6+1/(1+1/(1+1/(2*7+1))))))))))))))))))))
Input: 2+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(2*5+1/(1+1/(1+1/(2*6+1/(1+1/(1+1/(2*7+1))))))))))))))))))))
RPN string: 211121111141111161111181111125*1111126*1111127*1+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value: 2.7182818284590455
(Note:e = 2.718281828459045235260287471352...)
3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))))))
Input: 3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))))))
RPN string: 317153*111498*1+*/+/+/+/+
Value: 3.1415926530119025
3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/(2*7+1/(2+1)))))))))))))
Input: 3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/(2*7+1/(2+1)))))))))))))
RPN string: 317153*111498*1+*11111112111311127*121+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value: 3.141592653589793
(Note:pi = 3.141592653589793238462643383279...)
1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1)))))))))))))))))))))))))))))))))))
Input: 1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1)))))))))))))))))))))))))))))))))))
RPN string: 111111111111111111111111111111111111111111111111111111111111111111111111+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value: 1.618033988749894
(Note: f = 1.618033988749894848204586834365 ...
= (0.5)*(1 + sqrt(5)) )
^C (ctrl-C)
优质内容筛选与推荐>>1、第1次作业－Numpy练习
2、[转]分布式系统的特点以及设计理念
3、linux——jdk，mysql，tomcat
4、java - day008 - 接口,内部类
5、AMD XP sp2 设置(转载)