# String expression evaluation

It can carry out addition, subtraction, multiplication and division, exponential operation, power operation, factorial operation, trigonometric function operation and logarithmic function operation.

Because the previous ones are easy to handle, here I mainly explain that the operation of trigonometric function and logarithmic function can adopt the idea of recursion.

(for convenience of explanation, this article directly uses an example to illustrate that subscripts are counted from 0)

First, there is an original expression, such as sin(1+2)*ln(2*3)+5. This expression is difficult to calculate all at once, but infix expressions without functions (such as 1 + 2 and sin(1+2) in sin(1+2)) can be converted into suffix expressions, and then calculated.

Here, we define four stacks, which are the expression stack of the operation expression, the two position stacks of the sub expression in its parent expression (for sin(1+2), 0 and 7 in the 0th and 7th of its parent expression respectively), and the function stack represented by the sub expression (for sin(1+2), the "sin" is stored in the stack)

```        Stack<String> functionStack = new Stack<>();//Save expression
Stack<Integer> leftStack = new Stack<>();//Save sub expression left
Stack<Integer> rightStack = new Stack<>();//Save sub expression right
Stack<String> numStack = new Stack<>();//Function with sub expression
String currentStr;//Current expression. All operations are based on the current expression```

Then there is a problem now. First, how to locate the sub expression. This paper uses this traversal to scan the string from left to right. If sin, cos, tan and LN are encountered, it returns its position in the parent string, push them into leftStack and rightStack respectively, and then push the parent expression into functionStack, Then push the function of the sub expression into numStack. Set the current string to the infix expression without function (such as 1 + 2 in sin(1+2). After calculating 1 + 2, replace sin(3) with the parent string (0.141*ln(2*3)+5). Everything else is done according to the gourd.

```functionStack.push(currentStr);
int begin = functionBorder(currentStr);
int end = functionBorder(currentStr, begin);
leftStack.push(begin);
rightStack.push(end);
numStack.push(numOfFunction(currentStr));
currentStr = currentStr.substring(begin + numStack.peek().length() + 1, end);//Get the string in this function```

Therefore, we can calculate sin(1+2) and ln(2*3), so this expression is easy to calculate, that is 0.141 * 1.098 + 5. This formula is very simple. This is a standard expression with only addition, subtraction, multiplication and division.

Others may say that if it is function nesting (e.g. sin(cos(x))), what is it? This is the charm of recursion, which is the same as the post order traversal of recursive tree.

```    public static String calculate(String currentStr) {

Stack<String> functionStack = new Stack<>();//Save expression
Stack<Integer> leftStack = new Stack<>();//Save sub expression left
Stack<Integer> rightStack = new Stack<>();//Save sub expression right
Stack<String> numStack = new Stack<>();//Function with sub expression

while (!isNumber(currentStr) || !functionStack.isEmpty()) {

if (containsSpecialStr(currentStr)) {//There are special functions
functionStack.push(currentStr);
int begin = functionBorder(currentStr);
int end = functionBorder(currentStr, begin);
leftStack.push(begin);
rightStack.push(end);
numStack.push(numOfFunction(currentStr));
currentStr = currentStr.substring(begin + numStack.peek().length() + 1, end);//Get the string in this function
//functionStack.push(currentStr);
} else {//No special functions exist
double calculate = Double.parseDouble(calculateWithoutStr(currentStr));//This function calculates a simple infix expression
String suan = "";
if (!numStack.isEmpty())//Without special functions
suan = numStack.pop();
switch (suan) {
case "cos":
calculate = Math.cos(calculate);
break;
case "sin":
calculate = Math.sin(calculate);
break;
case "tan":
calculate = Math.tan(calculate);
break;
case "ln":
calculate = Math.log(calculate);
break;
}
if (!functionStack.isEmpty()) {
currentStr = new StringBuilder(functionStack.pop()).replace(leftStack.pop(),
rightStack.pop() + 1, String.valueOf(calculate)).toString();
} else
currentStr = String.valueOf(calculate);
}
}
return currentStr;
}
//Regular expression confirms whether the expression is a floating point number
public static boolean isNumber(String str) {
String reg = "^[-+]?[0-9]+(.[0-9]+)?\$";
return str.matches(reg);
}

private static boolean containsSpecialStr(String str) {
return str.contains("sin") || str.contains("cos") || str.contains("ln") || str.contains("tan");
}

private static int functionBorder(String expression) {
char[] chars = expression.toCharArray();
for (int j = 0; j < chars.length; j++) {//+ - * / ^ ! ( )
if (!(isDigit(chars[j]) || chars[j] == '+' || chars[j] == '-' || chars[j] == '*' || chars[j] == '/' ||
chars[j] == '!' || chars[j] == '^' || chars[j] == '(' || chars[j] == ')' || chars[j] == '.')) {
return j;//If it is a letter, it returns to get the starting character
}
}
return -1;//Indicates no letters
}

private static String numOfFunction(String expression) {
char[] chars = expression.toCharArray();
for (char aChar : chars) {
if (aChar == 'c')//If it is a letter, it returns to get the starting character
return "cos";
else if (aChar == 's')
return "sin";
else if (aChar == 't')
return "tan";
else if (aChar == 'l')
return "ln";
}
return "";//Indicates no letters
}

private static int functionBorder(String expression, int begin) {//Start from 0
int leftParenthesis = 1;
char current;
int end = begin;
boolean flag = true;
while (leftParenthesis != 0 && end + 1 != expression.length()) {
end = end + 1;
current = expression.charAt(end);
if (current == '(') {
leftParenthesis++;
if (flag) {
leftParenthesis--;
flag = false;
}
} else if (current == ')')
leftParenthesis--;
}
if (leftParenthesis != 0)
throw new RuntimeException("Error in expression,The brackets are missing");
return end;
}```

In this function, except for the function to calculate the simple infix expression, everything else is given

`double calculate = Double.parseDouble(calculateWithoutStr(currentStr));`

Only the calculateWithoutStr() function is not given, which can be found casually on the Internet.

Keywords: Java Algorithm

Added by tdnxxx444 on Sat, 12 Feb 2022 15:11:26 +0200