/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
System.
out.
println(eval
("2^3^2")); // this should be 512, i.e. 2^(3^2) System.
out.
println(eval
("2*3^2")); // this should be 18, i.e. 2*(3^2) }
static double eval
(final String str
) { int pos = -1, ch;
void nextChar() {
ch = (++pos < str.length()) ? str.charAt(pos) : -1;
}
boolean eat(int charToEat) {
while (ch == ' ') nextChar();
if (ch == charToEat) {
nextChar();
return true;
}
return false;
}
double parse() {
nextChar();
double x = parseExpression();
return x;
}
// Grammar:
// expression = term | expression `+` term | expression `-` term
// term = factor | term `*` factor | term `/` factor
// factor = `+` factor | `-` factor | `(` expression `)`
// | number | functionName factor | factor `^` factor
double parseExpression() {
double x = parseTerm();
for (;;) {
if (eat('+')) x += parseTerm(); // addition
else if (eat('-')) x -= parseTerm(); // subtraction
else return x;
}
}
double parseTerm() {
double x = parseFactor();
for (;;) {
if (eat('*')) x *= parseFactor(); // multiplication
else if (eat('/')) x /= parseFactor(); // division
else if (eat
('^')) x
= Math.
pow(x, parseFactor
()); //exponentiation -> Moved in to here. So the problem is fixed else return x;
}
}
double parseFactor() {
if (eat('+')) return parseFactor(); // unary plus
if (eat('-')) return -parseFactor(); // unary minus
double x;
int startPos = this.pos;
if (eat('(')) { // parentheses
x = parseExpression();
eat(')');
} else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
x
= Double.
parseDouble(str.
substring(startPos,
this.
pos)); } else if (ch >= 'a' && ch <= 'z') { // functions
while (ch >= 'a' && ch <= 'z') nextChar();
String func
= str.
substring(startPos,
this.
pos); x = parseFactor();
if (func.
equals("sqrt")) x
= Math.
sqrt(x
); else if (func.
equals("sin")) x
= Math.
sin(Math.
toRadians(x
)); else if (func.
equals("cos")) x
= Math.
cos(Math.
toRadians(x
)); else if (func.
equals("tan")) x
= Math.
tan(Math.
toRadians(x
)); } else {
}
//if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation -> This is causing a bit of problem
return x;
}
}.parse();
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVN5c3RlbS5vdXQucHJpbnRsbihldmFsKCIyXjNeMiIpKTsgLy8gdGhpcyBzaG91bGQgYmUgNTEyLCBpLmUuIDJeKDNeMikKCQlTeXN0ZW0ub3V0LnByaW50bG4oZXZhbCgiMiozXjIiKSk7IC8vIHRoaXMgc2hvdWxkIGJlIDE4LCBpLmUuIDIqKDNeMikKCX0Kc3RhdGljIGRvdWJsZSBldmFsKGZpbmFsIFN0cmluZyBzdHIpIHsKICAgIHJldHVybiBuZXcgT2JqZWN0KCkgewogICAgICAgIGludCBwb3MgPSAtMSwgY2g7CgogICAgICAgIHZvaWQgbmV4dENoYXIoKSB7CiAgICAgICAgICAgIGNoID0gKCsrcG9zIDwgc3RyLmxlbmd0aCgpKSA/IHN0ci5jaGFyQXQocG9zKSA6IC0xOwogICAgICAgIH0KCiAgICAgICAgYm9vbGVhbiBlYXQoaW50IGNoYXJUb0VhdCkgewogICAgICAgICAgICB3aGlsZSAoY2ggPT0gJyAnKSBuZXh0Q2hhcigpOwogICAgICAgICAgICBpZiAoY2ggPT0gY2hhclRvRWF0KSB7CiAgICAgICAgICAgICAgICBuZXh0Q2hhcigpOwogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgIH0KCiAgICAgICAgZG91YmxlIHBhcnNlKCkgewogICAgICAgICAgICBuZXh0Q2hhcigpOwogICAgICAgICAgICBkb3VibGUgeCA9IHBhcnNlRXhwcmVzc2lvbigpOwogICAgICAgICAgICBpZiAocG9zIDwgc3RyLmxlbmd0aCgpKSB0aHJvdyBuZXcgUnVudGltZUV4Y2VwdGlvbigiVW5leHBlY3RlZDogIiArIChjaGFyKWNoKTsKICAgICAgICAgICAgcmV0dXJuIHg7CiAgICAgICAgfQoKICAgICAgICAvLyBHcmFtbWFyOgogICAgICAgIC8vIGV4cHJlc3Npb24gPSB0ZXJtIHwgZXhwcmVzc2lvbiBgK2AgdGVybSB8IGV4cHJlc3Npb24gYC1gIHRlcm0KICAgICAgICAvLyB0ZXJtID0gZmFjdG9yIHwgdGVybSBgKmAgZmFjdG9yIHwgdGVybSBgL2AgZmFjdG9yCiAgICAgICAgLy8gZmFjdG9yID0gYCtgIGZhY3RvciB8IGAtYCBmYWN0b3IgfCBgKGAgZXhwcmVzc2lvbiBgKWAKICAgICAgICAvLyAgICAgICAgfCBudW1iZXIgfCBmdW5jdGlvbk5hbWUgZmFjdG9yIHwgZmFjdG9yIGBeYCBmYWN0b3IKCiAgICAgICAgZG91YmxlIHBhcnNlRXhwcmVzc2lvbigpIHsKICAgICAgICAgICAgZG91YmxlIHggPSBwYXJzZVRlcm0oKTsKICAgICAgICAgICAgZm9yICg7OykgewogICAgICAgICAgICAgICAgaWYgICAgICAoZWF0KCcrJykpIHggKz0gcGFyc2VUZXJtKCk7IC8vIGFkZGl0aW9uCiAgICAgICAgICAgICAgICBlbHNlIGlmIChlYXQoJy0nKSkgeCAtPSBwYXJzZVRlcm0oKTsgLy8gc3VidHJhY3Rpb24KICAgICAgICAgICAgICAgIGVsc2UgcmV0dXJuIHg7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGRvdWJsZSBwYXJzZVRlcm0oKSB7CiAgICAgICAgICAgIGRvdWJsZSB4ID0gcGFyc2VGYWN0b3IoKTsKICAgICAgICAgICAgZm9yICg7OykgewogICAgICAgICAgICAgICAgaWYgICAgICAoZWF0KCcqJykpIHggKj0gcGFyc2VGYWN0b3IoKTsgLy8gbXVsdGlwbGljYXRpb24KICAgICAgICAgICAgICAgIGVsc2UgaWYgKGVhdCgnLycpKSB4IC89IHBhcnNlRmFjdG9yKCk7IC8vIGRpdmlzaW9uCiAgICAgICAgICAgICAgICBlbHNlIGlmIChlYXQoJ14nKSkgeCA9IE1hdGgucG93KHgsIHBhcnNlRmFjdG9yKCkpOyAvL2V4cG9uZW50aWF0aW9uIC0+IE1vdmVkIGluIHRvIGhlcmUuIFNvIHRoZSBwcm9ibGVtIGlzIGZpeGVkCiAgICAgICAgICAgICAgICBlbHNlIHJldHVybiB4OwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBkb3VibGUgcGFyc2VGYWN0b3IoKSB7CiAgICAgICAgICAgIGlmIChlYXQoJysnKSkgcmV0dXJuIHBhcnNlRmFjdG9yKCk7IC8vIHVuYXJ5IHBsdXMKICAgICAgICAgICAgaWYgKGVhdCgnLScpKSByZXR1cm4gLXBhcnNlRmFjdG9yKCk7IC8vIHVuYXJ5IG1pbnVzCgogICAgICAgICAgICBkb3VibGUgeDsKICAgICAgICAgICAgaW50IHN0YXJ0UG9zID0gdGhpcy5wb3M7CiAgICAgICAgICAgIGlmIChlYXQoJygnKSkgeyAvLyBwYXJlbnRoZXNlcwogICAgICAgICAgICAgICAgeCA9IHBhcnNlRXhwcmVzc2lvbigpOwogICAgICAgICAgICAgICAgZWF0KCcpJyk7CiAgICAgICAgICAgIH0gZWxzZSBpZiAoKGNoID49ICcwJyAmJiBjaCA8PSAnOScpIHx8IGNoID09ICcuJykgeyAvLyBudW1iZXJzCiAgICAgICAgICAgICAgICB3aGlsZSAoKGNoID49ICcwJyAmJiBjaCA8PSAnOScpIHx8IGNoID09ICcuJykgbmV4dENoYXIoKTsKICAgICAgICAgICAgICAgIHggPSBEb3VibGUucGFyc2VEb3VibGUoc3RyLnN1YnN0cmluZyhzdGFydFBvcywgdGhpcy5wb3MpKTsKICAgICAgICAgICAgfSBlbHNlIGlmIChjaCA+PSAnYScgJiYgY2ggPD0gJ3onKSB7IC8vIGZ1bmN0aW9ucwogICAgICAgICAgICAgICAgd2hpbGUgKGNoID49ICdhJyAmJiBjaCA8PSAneicpIG5leHRDaGFyKCk7CiAgICAgICAgICAgICAgICBTdHJpbmcgZnVuYyA9IHN0ci5zdWJzdHJpbmcoc3RhcnRQb3MsIHRoaXMucG9zKTsKICAgICAgICAgICAgICAgIHggPSBwYXJzZUZhY3RvcigpOwogICAgICAgICAgICAgICAgaWYgKGZ1bmMuZXF1YWxzKCJzcXJ0IikpIHggPSBNYXRoLnNxcnQoeCk7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChmdW5jLmVxdWFscygic2luIikpIHggPSBNYXRoLnNpbihNYXRoLnRvUmFkaWFucyh4KSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChmdW5jLmVxdWFscygiY29zIikpIHggPSBNYXRoLmNvcyhNYXRoLnRvUmFkaWFucyh4KSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChmdW5jLmVxdWFscygidGFuIikpIHggPSBNYXRoLnRhbihNYXRoLnRvUmFkaWFucyh4KSk7CiAgICAgICAgICAgICAgICBlbHNlIHRocm93IG5ldyBSdW50aW1lRXhjZXB0aW9uKCJVbmtub3duIGZ1bmN0aW9uOiAiICsgZnVuYyk7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB0aHJvdyBuZXcgUnVudGltZUV4Y2VwdGlvbigiVW5leHBlY3RlZDogIiArIChjaGFyKWNoKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgLy9pZiAoZWF0KCdeJykpIHggPSBNYXRoLnBvdyh4LCBwYXJzZUZhY3RvcigpKTsgLy8gZXhwb25lbnRpYXRpb24gLT4gVGhpcyBpcyBjYXVzaW5nIGEgYml0IG9mIHByb2JsZW0KCiAgICAgICAgICAgIHJldHVybiB4OwogICAgICAgIH0KICAgIH0ucGFyc2UoKTsKfQp9