IT公司面试题收集整理-数据结构有关复习-算术表达式求值算法（带括号递归运算）

IT公司面试题收集整理---数据结构相关复习---算术表达式求值算法（带括号递归运算）

首先声明，这仅仅是一个算法的雏形，实用率几乎为0。我只说这个思想。代码是用java写的，可以运行，但是表达式和中间值不能为负数【因为我用的java的字符串截取，如果使用C语言的话，在不带括号的情况中，就没有这个问题了，也可以为负数】，下面我写出我的想法，然后你就知道为什么不能为负数了。

第一：判断有没有括号，有的话，遇到一个右括号，那么就截取对应的左括号与右括号之间的字符串，还要让字符串加一个=。【因为没有括号的方法中限制的】

第二：如果现在只有加减乘除的话，比如说1+2*3+4+5-5=，就进入循环

第三：分为两个栈，遇到一个符号的时候，先放数字栈数据，然后比较符号栈的顶部，与即将放入栈的符号，进行比较。如果即将进栈的优先级比顶部的优先级低，那么

数字栈出两个，符号栈出一个，进行计算，结果放到数字栈，即将放入栈的符号现在也放入栈。

第四：遇到等号的话，全部出栈。栈为空的话，返回数字栈的第一个值。【即最终结果】

package 计算器;

public class Demo {
	public double number[] = new double[6];// 数字栈
	public char sign[] = new char[6];// 符号栈,*/=优先级大于+-优先级
	public int topNum = -1;// 头指针
	public int topSign = -1;// 头指针

	// 表达式求值，带括号算法,注意：表达式一定要正确，并且不能出现负数，因为这个算法用的是字符串截取
	public double evaluation(String string) throws Exception {// 参数代表正确的表达式
		double result = 0;
		// 如果式子中包含括号，截取括号匹配中的字符串
		if (string.contains("(") || string.contains(")")) {
			int temp = 0;
			for (int i = 0; i < string.length(); i++) {
				if (string.charAt(i) == '(') {// 碰到左括号，记录下来
					temp = i;
					continue;
				}
				if (string.charAt(i) == ')') {// 碰到右括号，进行递归，实际上相当于出栈
					string = string.substring(0, temp)
							+ evaluation(string.substring(temp + 1, i) + "=")// 加个等号继续递归
							+ string.substring(i + 1);
					System.out.println(string);
					i = -1;
					continue;
				}
			}
		}
		// 现在式子中只有加减乘除的话,进行栈的操作
		for (int i = 0; i < string.length(); i++) {
			switch (string.charAt(i)) {
			case '+':
			case '-':
			case '*':
			case '/':
			case '=':
				result = calculate(string, i, string.charAt(i));
				string = string.substring(i + 1);
				i = -1;
				break;
			default:
				break;
			}
		}
		return result;
	}

	private double calculate(String string, int sub, char signal) {
		double x = Double.parseDouble(string.substring(0, sub));
		number[++topNum] = x;// 数字进栈
		if (topSign == -1) {// 如果符号栈为空
			sign[++topSign] = signal;
			return number[topNum];
		}
		if (signal == '=') {// 计算数值
			while (topSign != -1) {
				if (sign[topSign] == '+') {
					number[topNum - 1] += number[topNum];
				} else if (sign[topSign] == '-') {
					number[topNum - 1] -= number[topNum];
				} else if (sign[topSign] == '*') {
					number[topNum - 1] *= number[topNum];
				} else if (sign[topSign] == '/') {
					number[topNum - 1] /= number[topNum];
				}
				topSign--;
				topNum--;// 退栈
			}
			return number[topNum];
		}
		if (comparePriority(signal, sign[topSign])) {
			// 退栈，并且将计算结果放入数字栈中
			if (sign[topSign] == '+') {
				number[topNum - 1] += number[topNum];
			} else if (sign[topSign] == '-') {
				number[topNum - 1] -= number[topNum];
			} else if (sign[topSign] == '*') {
				number[topNum - 1] *= number[topNum];
			} else if (sign[topSign] == '/') {
				number[topNum - 1] /= number[topNum];
			}
			sign[topSign] = signal;// 符号栈应该是topSign--【退栈】,然后++【进栈】，在这里我们直接换符号了
			topNum--;// 退栈
		} else {
			sign[++topSign] = signal;// 进栈
		}
		return number[topNum];
	}

	/**
	 * 比较a,b的优先级if(a<==b)那么返回true
	 */
	boolean comparePriority(char a, char top) {
		boolean judge = false;
		if ((a == '+' || a == '-')
				&& (top == '+' || top == '-' || top == '*' || top == '/')) {
			judge = true;
		}
		if ((a == '*' || a == '/') && (top == '*' || top == '/')) {
			judge = true;
		}
		return judge;
	}

	public static void main(String[] args) {
		try {
			System.out.println(new Demo().evaluation("1*(2+3/(5-2))+4+5="));
		} catch (Exception e) {
			e.printStackTrace();
			System.out.println("对不起，表达式不是标准的正数运算表达式，过程值也不能为负");
		}
	}
}

看到这里，你可能会觉得我这个局限比较大，确实是这样，这个确实比较水。因为还要考虑好多种情况，我只把这个算法的思想写了出来。真正要写好这个表达式求值的话，还真是不容易。

如果哪位大哥能给我一个不错的源码，我就感激不尽了。

还有就是，我听人说，这个带括号的，不用递归的话，可以用三个栈来进行操作，可能我智力有限吧，实在是想不出来怎么操作三个栈才能算出来，哪个大哥指点一下，我就不胜感激了。