笔试题：编程计算一个字符串类型的四则运算表达式的值
昨天下午去面试了一家利用JavaSE平台开发软件的公司，进门就让在电脑上做一套测试题，电脑不能上网。磨了两个小时后交卷走了，那套题做得不理想，估计没指望了。现在把题拿来和大家分享交流一下。
其中有一道编程题，题目如下：
编程计算一个字符串类型的四则运算表达式的值（暂不考虑有括号的情况），如：1+2*3-4/2
当时我只把大概的思路写了。回家后，整理了下，把代码写了出来，现在贴出来，希望和大家分享交流。各位有什么好的思路或者建议，欢迎发表意见。
/**
* 问题:
* 编写算法实现计算一个包含加减乘除四则运算的字符串表达式的值（暂不考虑括号）。例如：2+5*4-6/2
* 思路：
* 整个表达式分四趟运算，一趟计算乘法，二趟计算除法，三趟计算加法，四趟计算减法。
* 每一趟从头开始截取一个最简表达式（两个数和一个运算符）运算，将运算结果放回表达式原位置，然后再截取计算，这个过程递归进行。
* @author Jeby
*
*/
public class Arithmetic {
/**
* @param args
*/
public static void main(String[] args) {
String ex = "0.5+2*4-2.5*4/5";
System.out.println(ex+" = "+complete(ex));
}
public static double complete(String args) {
String strResult = "";
char[] operators = {'*','/','+','-'};
for(int i=0;i<operators.length;i++) {
strResult = subComplete(args,operators[i]);
args = strResult;
}
return Double.parseDouble(strResult);
}
public static String subComplete(String args,char opera) {
int operateIndex = 0; //运算符索引
int temp = 0; //临时变量，存放索引值
double a = 0d; //数值a
double b = 0d; //数值b
String beforeOperaString = ""; //运算符之前的字符串
String afterOperaString = ""; //运算符之后的字符串
String strNumA = ""; //字符串类型的数字a
String strNumB = ""; //字符串类型的数字b
String strLeft = ""; //正在计算的最简表达式左边的串
String strRight = ""; //正在计算的最简表达式右边的串
String result = ""; //运算结果（运算结果=最简表达式之前的字符串+最简表达式的值+最简表达式之后的字符串）
operateIndex = args.indexOf(opera);
if(operateIndex==-1) {
return args;
}
//以运算符为界将字符串分为两节
beforeOperaString = args.substring(0, operateIndex);
afterOperaString = args.substring(operateIndex+1);
//取出运算符两边的数，并得到正在计算的最简表达式左右两边的表达式串
temp = findCharIndex(beforeOperaString,false);
strNumA= beforeOperaString.substring(temp==0?temp:temp+1);
if(temp!=0) {
strLeft = beforeOperaString.substring(0, temp+1);
}
temp = findCharIndex(afterOperaString,true);
strNumB = afterOperaString.substring(0, temp==0?afterOperaString.length():temp);
if(temp!=0) {
strRight = afterOperaString.substring(temp);
}
a = Double.parseDouble(strNumA);
b = Double.parseDouble(strNumB);
if(opera=='*') result = strLeft+(a*b)+strRight;
else if(opera=='/') result = strLeft+(a/b)+strRight;
else if(opera=='+') result = strLeft+(a+b)+strRight;
else if(opera=='-') result = strLeft+(a-b)+strRight;
//打印
System.out.println(result);
return subComplete(result,opera);
}
/**
* 获取一个表达式中第一个或者最后一个运算符的索引值
* @param str - 被检查的字符串
* @param fromBegin - 如果true，用index查找最简表达式右边第一个运算符；
* 如果false，用lastIndex查找最简表达式左边边最后一个运算符。
* @return 运算符索引
*/
public static int findCharIndex(String str,boolean fromBegin) {
int index = 0;
int temp = 0;
if(fromBegin) {
temp = str.indexOf('*');
index = (temp!=-1)?temp:index;
temp = str.indexOf('/');
index = (temp!=-1 && (index==0 || temp<index))?temp:index;
temp = str.indexOf('+');
index = (temp!=-1 && (index==0 || temp<index))?temp:index;
temp = str.indexOf('-');
index = (temp!=-1 && (index==0 || temp<index))?temp:index;
return index;
}
temp = str.lastIndexOf('*');
index = (temp!=-1)?temp:index;
temp = str.lastIndexOf('/');
index = (temp!=-1 && (index==0 || temp>index))?temp:index;
temp = str.lastIndexOf('+');
index = (temp!=-1 && (index==0 || temp>index))?temp:index;
temp = str.lastIndexOf('-');
index = (temp!=-1 && (index==0 || temp>index))?temp:index;
return index;
}
}
package cn.zhangao;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class TestCalString {
public static void main(String[] args) throws ScriptException {
String ex = "0.5+2*4-2.5*4/5";
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("javascript");
System.out.print(engine.eval(ex));
}
}
import java.util.Stack;
import java.util.Stack;
public class Test{
public static void TrnsInToSufix(String IFX,String []PFX)//PFX放后缀表达式，IFX为中缀表达式
{
StringBuffer numBuffer = new StringBuffer();// 用来保存一个数的
Stack<String> s=new Stack<String>();//放操作符
String a;
s.push("=");//第一个为等号
int i=0,j=0;
char ch;
for(i=0;i<IFX.length();)
{
ch=IFX.charAt(i);
switch(ch)
{
case '0':case '1':case '2':
case '3':case '4':case '5':
case '6':case '7':case '8':
case '9':
while(Character.isDigit(ch)
[解决办法]
ch=='.')//拼数
{
numBuffer.append(ch); // 追加字符
ch = IFX.charAt(++i);
}
PFX[j++]=numBuffer.toString();//break;
numBuffer = new StringBuffer(); //清空已获取的运算数字
continue; //这里要重新循环，因为i已经增加过了
case '(':
s.push("(");break;
case ')':
while(s.peek()!="(")
PFX[j++]=s.pop();
break;
case '+':
case '-':
while(s.size()>1&&s.peek()!="(")
PFX[j++]=s.pop();
a=String.valueOf(ch);
s.push(a);break;
case '*':
case '/':
while(s.size()>1&&(s.peek()=="*")
[解决办法]
s.peek()=="/"
[解决办法]
s.peek()=="s"
[解决办法]
s.peek()=="c"
[解决办法]
s.peek()=="t"
[解决办法]
s.peek()=="^"
[解决办法]
s.peek()=="√")//优先级比较，与栈顶比较，
PFX[j++]=s.pop();//当前操作符优先级大于等于栈顶的弹出栈顶
a=String.valueOf(ch);
s.push(a);break;
case 's':
case 'c':
case 't'://三角函数
while(s.size()>1&&(s.peek()=="s"
[解决办法]
s.peek()=="c"
[解决办法]
s.peek()=="t"
[解决办法]
s.peek()=="^"
[解决办法]
s.peek()=="√"))//优先级比较，与栈顶，大于等于的弹出
PFX[j++]=s.pop();
a=String.valueOf(ch);
s.push(a);break;
case '^':// 幂
case '√':// 开方
while(s.size()>1&&(s.peek()=="^"
[解决办法]
s.peek()=="√"))
PFX[j++]=s.pop();
a=String.valueOf(ch);
s.push(a);break;
}
i++;
}
while(s.size()>1)
PFX[j++]=s.pop();
PFX[j]="=";
}
public static String Evaluate (String []PFX)//后缀表达式求值
{
int i=0;
double x1,x2,n;
String str;
Stack<String> s= new Stack<String>();
while(PFX[i]!="=")
{
str=PFX[i];
switch(str.charAt(0))
{
case '0':case '1':case '2':
case '3':case '4':case '5':
case '6':case '7':case '8':
case '9':
s.push(str);break;
case '+':
x1=Double.parseDouble(s.pop());
x2=Double.parseDouble(s.pop());
n=x1+x2;
s.push(String.valueOf(n));break;
case '-':
x1=Double.parseDouble(s.pop());
x2=Double.parseDouble(s.pop());
n=x2-x1;
s.push(String.valueOf(n));break;
case '*':
x1=Double.parseDouble(s.pop());
x2=Double.parseDouble(s.pop());
n=x1*x2;
s.push(String.valueOf(n));break;
case '/':
x1=Double.parseDouble(s.pop());
x2=Double.parseDouble(s.pop());
n=x2/x1;
s.push(String.valueOf(n));break;
case 's':
x1=Double.parseDouble(s.pop());
n=Math.sin(x1 * Math.PI / 180);
s.push(String.valueOf(n));break;
case 'c':
x1=Double.parseDouble(s.pop());
n=Math.cos(x1 * Math.PI / 180);
s.push(String.valueOf(n));break;
case 't':
x1=Double.parseDouble(s.pop());
n=Math.tan(x1 * Math.PI / 180);
s.push(String.valueOf(n));break;
case '√':
x1=Double.parseDouble(s.pop());
n=Math.sqrt(x1);
s.push(String.valueOf(n));break;// 开方
case '^':
x1=Double.parseDouble(s.pop());
x2=Double.parseDouble(s.pop());
n=Math.pow(x2, x1);
s.push(String.valueOf(n));break;
}
i++;
}
return s.pop();
}
public static void main(String[] args) {
Test eval = new StrTest();
String s="1+2*3=";//sin45*2,sin 要用string.replace转换成 s
String[] PFX = new String[100];
Test.TrnsInToSufix(s, PFX);
System.out.println(Test.Evaluate(PFX));
}
}
import java.util.*;
public class CalExpression {
// 整体运算
private double calculate(String total) {
int position1 = 0;
int position2 = 0;
// 分析表达式是否有括号
Boolean had = false;
for (int i = 0; i < total.length(); i++) {
if (total.charAt(i) == '(')
had = true;
}
// 查一下为什么indexof在此不能用~~~~谁知道的话告诉一声，下列代码错在哪里~~~
// 用错这里 查了一小时菜查出错误
if (had == true)// 只需处理第一个括号，然后递归调用自身，有括号继续处理，没括号就得果
{
for (int i = 0; i < total.length(); i++) {
if (total.charAt(i) == '(') {
position1 = i;
continue;
}
if (total.charAt(i) == ')') {
position2 = i;
break;
}
}
// 这句重点，有点长
return calculate(total.substring(0, position1).trim()
+ calculate(total.substring(position1 + 1, position2)
.trim())
+ total.substring(position2 + 1, total.length()).trim());
} else
return returnInner(total);
}
// 针对括号内的运算,即未带括号的表达式~~~有的话递归调用自身
private double returnInner(String expression) {
double result = 0;
int op1 = 0;
int op2 = 0;
char operator = ' ';
int count = 0;
// 此循环用于获得前两个操作符的位置
for (int i = 0; i < expression.length(); i++) {
operator = expression.charAt(i);
if (operator == 42
[解决办法]
operator == 43
[解决办法]
operator == 45
[解决办法]
operator == 47) {
if (count == 0) {
op1 = i;
count++;
continue;
}
if (count == 1) {
op2 = i;
break;
}
}
}
// 判断第一个操作符，并用递归计算整个表达式~~~~~
// 即把未带括号的表达式拆成第一个数与其后面的表达式 进行运算
// 这整个算法很经典~~~~呵呵~~有参考网上的解析~~~觉得这个最短最好用
// 当然，括号太多~~仔细辨清各个整体~~~
operator = expression.charAt(op1);
if (operator == '+') {
result = Double.parseDouble(expression.substring(0, op1).trim());// 获取第一个数
if (op2 > 0)
result += returnInner(expression.substring((op1 + 1),
expression.length()));// 有两个以上操作符~~~递归
else
result += Double.parseDouble(expression.substring(op1 + 1,
expression.length()).trim());// 只有一个+号
} else if (operator == '-') // 同+运算
{
result = Double.parseDouble(expression.substring(0, op1).trim());
if (op2 > 0)
result -= returnInner(expression.substring((op1 + 1),
expression.length()));
else
result -= Double.parseDouble(expression.substring(op1 + 1,
expression.length()).trim());
} else if (operator == '*') {
if (op2 > 0)// 有两个以上操作符，先第一个数*第二个数 然后在与后面的字符组成一个表达式，带入递归 有用空格特意局开整体
result = returnInner((Double.parseDouble(expression.substring(
0, op1).trim()) * Double.parseDouble(expression
.substring((op1 + 1), op2)))
+ expression.substring(op2, expression.length()));
else
result = (Double.parseDouble(expression.substring(0, op1)
.trim()) * Double.parseDouble(expression.substring(
(op1 + 1), expression.length())));
return result;
} else if (operator == '/') // 同*运算
{
if (op2 > 0)
result = returnInner((Double.parseDouble(expression.substring(
0, op1).trim()) / Double.parseDouble(expression
.substring((op1 + 1), op2)))
+ expression.substring(op2, expression.length()));
else
result = (Double.parseDouble(expression.substring(0, op1)
.trim()) / Double.parseDouble(expression.substring(
(op1 + 1), expression.length())));
}
return result;
}
public static void main(String[] args) {
System.out.println("Input the expression");// 手动输入表达式
Scanner in = new Scanner(System.in);
String exp = in.nextLine();
CalExpression cal = new CalExpression();
System.out.println(cal.calculate(exp));
}
}
public class Test {
public static void main(String[] args) {
String ex = "0.5+2*4-2.5*4/5";
System.out.println(c(ex));
}
public static String c(String ex){
char[] ch={'*','/','+','-'};
for (int j = 0; j < 4; j=j+2) {
System.out.println();
for (int i = 0; i < ex.length(); i++) {
if(ch[j]==ex.charAt(i)
[解决办法]
ch[j+1]==ex.charAt(i)){
int b = i;
String temp="";
String temp2="";
while(b>0){
b--;
if(ex.charAt(b)!='*'&&ex.charAt(b)!='/'&&ex.charAt(b)!='+'&&ex.charAt(b)!='-'){
temp+= ex.charAt(b);
}else{
break;
}
}
temp = fanZhuan(temp);
b = i;
while(b<ex.length()-1){
b++;
if(ex.charAt(b)!='*'&&ex.charAt(b)!='/'&&ex.charAt(b)!='+'&&ex.charAt(b)!='-'){
temp2+= ex.charAt(b);
}else{
break;
}
}
if(!temp.matches("[\\d]+[\\.]?[\\d]*"))temp2 = fanZhuan(temp2);
switch (ex.charAt(i)) {
case '*':
ex = ex.replace(temp+ch[j]+temp2, String.valueOf(Float.valueOf(temp)*Float.valueOf(temp2)));
break;
case '/':
ex = ex.replace(temp+ch[j+1]+temp2, String.valueOf(Float.valueOf(temp)/Float.valueOf(temp2)));
break;
case '+':
ex = ex.replace(temp+ch[j]+temp2, String.valueOf(Float.valueOf(temp)+Float.valueOf(temp2)));
break;
case '-':
ex = ex.replace(temp+ch[j+1]+temp2, String.valueOf(Float.valueOf(temp)-Float.valueOf(temp2)));
break;
}
if(ex.matches("[\\d]+[\\.]?[\\d]*")){
break;
}else{
i=0;
}
}
}
}
return ex;
}
static String fanZhuan(String str){
String temp = "";
for (int i = str.length()-1; i >=0; i--) {
temp+=str.charAt(i);
}
return temp;
}
}
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Test{
public static void main(String[] args){
String result = compute("3*4-2*4-3*4+5.5");
//System.out.println(result);
}
public static String compute(String expression){
expression = "(" + expression + ")";
String regex = "(.*?)(\\([^()]+\\))(.*)";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(expression);
while(matcher.find()){
expression = matcher.group(1) + compute1(matcher.group(2)) + matcher.group(3);
matcher = pattern.matcher(expression);
System.out.println(expression);
}
return expression;
}
private static String compute1(String expression){
/*
计算没有包含括号的情况下的结果
*/
expression = expression.replaceAll("[( )]","");
String regex = "^(.*?)(\\d+(?:\\.\\d+)?)([/*])(-?\\d+(?:\\.\\d+)?)(.*)";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(expression);
double value1 = 0.0;
double value2 = 0.0;
String temp = null;
while(matcher.find()){
value1 = Double.valueOf(matcher.group(2));
value2 = Double.valueOf(matcher.group(4));
if(matcher.group(3).equals("*")){
temp = (value1 * value2) + "";
}else{
temp = (value1 / value2) + "";
}
expression = matcher.group(1) + temp + matcher.group(5);
expression = expression.replaceAll("--","+");
matcher = pattern.matcher(expression);
}
//System.out.println(expression);
regex = "^(.*?)((?:(?=[-+*/])-)?\\d+(?:\\.\\d+)?)([-+])(-?\\d+(?:\\.\\d+)?)(.*)";
pattern = Pattern.compile(regex);
matcher = pattern.matcher(expression);
while(matcher.find()){
value1 = Double.valueOf(matcher.group(2));
value2 = Double.valueOf(matcher.group(4));
if(matcher.group(3).equals("+")){
temp = (value1 + value2) + "";
}else{
temp = (value1 - value2) + "";
}
expression = matcher.group(1) + temp + matcher.group(5);
matcher = pattern.matcher(expression);
}
expression = expression.replaceAll("\\+","");
return expression;
}
}
