求助啊:面试题目:要求:输入一条公式,如”1+2+(3+4*(5+6)/7)*8+9.1”得到正确的返回值。

Question

公式解析算法实现题目要求:输入一条公式,如”1+2+(3+4*(5+6)/7)*8+9.1”得到正确的返回值。
补充：考虑支持变量，函数等扩展要求，不要使用动态编译等脚本技术，要求自解析完成

Answer 1

参考一下：
http://www.chenjiliang.com/article/View.aspx?ArticleID=2671

Answer 2

using System;
using System.Collections.Generic;
using System.Text;namespace ExpressionParse
{
    //定义文法表示：
    //expr->statement{+statement}{-statement}
    //statement->operand{*operand}{/operand}
    //operand->num|(expr)    public class Parser
    {
        #region 私有成员        /// <summary>
        /// 需要解析的表达式
        /// </summary>
        private string expression = null;        /// <summary>
        /// 表达式的当前索引
        /// </summary>
        private int index = 0;        /// <summary>
        /// 用于保存解析出来的符号
        /// </summary>
        private string token = string.Empty;        /// <summary>
        /// 解析出来的单词符号类型
        /// </summary>
        private TokenType type = TokenType.Empty;        #endregion        #region 构造函数
        public Parser(string expression)
        {
            this.expression = expression;
        }
        #endregion        #region 公有方法        /// <summary>
        /// 提供给外部调用的解析方法
        /// </summary>
        /// <returns>表达式的计算结果</returns>
        public double Parse()
        {
            if (expression == null || expression.Trim().Length == 0)
                throw new Exception("没有输入字符串!");
            GetToken();
            if (type == TokenType.Empty)
            {
                throw new Exception("没有输入表达式");
            }            double result = ParseExpression();
            if (type != TokenType.Empty)
            {
                throw new Exception("表达式出现语法错误");
            }
            return result;
        }        #endregion        #region 解析表达式expr->statement{+statement}{-statement}        /// <summary>
        /// 解析表达式expr->statement{+statement}{-statement}
        /// </summary>
        /// <returns>表达式的计算值</returns>
        private double ParseExpression()
        {
            //op是记录操作符号(+-*/>)的字符,下同
            string op;
            double result = ParseStatement();
            if (type == TokenType.Empty)
                return result;            //循环计算statement的值
            while ((op = token) == "+" || op == "-")
            {
                GetToken();
                if (op == "+")
                {
                    result = result + ParseStatement();
                }
                else if (op == "-")
                {
                    result = result - ParseStatement();
                }
                if (type == TokenType.Empty)
                    break;
            }
            return result;
        }        #endregion        #region 解析statement->operand{*operand}{/operand}        /// <summary>
        /// 解析表达式中的项,statement->operand{*operand}{/operand}
        /// </summary>
        /// <returns>项statement的计算值</returns>
        private double ParseStatement()
        {
            double result = ParseOperand();
            string op = token;
            if (type == TokenType.Empty)
                return result;            //循环计算operand的值
            while ((op = token) == "*" || op == "/")
            {
                GetToken();
                if (op == "*")
                    result = result * ParseOperand();
                else if (op == "/")
                {
                    //处理除0，默认除0的话返回0
                    double partialResult = ParseOperand();
                    if (partialResult != 0)
                    {
                        result = result / partialResult;
                    }
                    else
                    {
                        return 0;
                    }
                }
                if (type == TokenType.Empty)
                    break;
            }
            return result;
        }
        #endregion        #region 解析operand->num|(expr)        /// <summary>
        /// 解析表达式中的项,operand->num|(expr)
        /// </summary>
        /// <returns>项operand的计算值</returns>
        private double ParseOperand()
        {
            double result = 0;            if (type == TokenType.Num)
            {
                result = double.Parse(token);
                GetToken();
            }            //如果type为左括号,递归调用ParseExpression
            else if (type == TokenType.LeftParentheses)
            {
                GetToken();
                result = ParseExpression();
                CheckRightParentheses();
                GetToken();
            }             //如果是单独的+-号,需要进行一些处理
            else if (token == "+" || token == "-")
            {
                string op = token;
                GetToken();
                result = ParseStatement();
                if (op == "-")
                    result = -result;
            }
            return result;
        }        #endregion       

Answer 3

 #region 词法分析        /// <summary>
        /// 每次得到下一个词。
        /// </summary>
        private void GetToken()
        {
            token = "";
            type = TokenType.Empty;
            while (index < expression.Length && expression[index] == ' ')
                index++;
            if (index == expression.Length)
            {
                return;
            }
            //判断是否为操作符
            if (IsDelim(expression[index]))
            {
                token += expression[index];
                index++;
                type = TokenType.Operators;
            }
            //判断是否为左括号
            else if (expression[index] == '(')
            {
                token += expression[index];
                index++;
                type = TokenType.LeftParentheses;
            }
            //判断是否为右括号
            else if (expression[index] == ')')
            {
                token += expression[index];
                index++;
                type = TokenType.RightParentheses;
            }
            //判断是否为数字
            else if (char.IsNumber(expression[index]))
            {
                while (char.IsNumber(expression[index]))
                {
                    token += expression[index];
                    index++;
                    if (index >= expression.Length)
                        break;
                }
                if (index < expression.Length && expression[index] == '.')
                {
                    token += expression[index];
                    index++;
                    while (char.IsNumber(expression[index]))
                    {
                        token += expression[index];
                        index++;
                        if (index >= expression.Length)
                            break;
                    }
                }
                type = TokenType.Num;
            }
            else
            {
                throw new Exception("输入错误");
            }
        }
        #endregion        #region 私有方法
        /// <summary>
        /// 判断一个字符是否为操作符。
        /// </summary>
        /// <param name="c"></param>
        /// <returns></returns>
        private bool IsDelim(char c)
        {
            //s代表需要支持的操作符。
            string s = "+-*/";
            return s.IndexOf(c) != -1;
        }
        /// <summary>
        /// 检查是否有右边括号')'。
        /// </summary>
        private void CheckRightParentheses()
        {
            if (type != TokenType.RightParentheses)
            {
                throw new Exception("解析出现错误,缺少一个')'!");
            }
        }        #endregion
    }    /// <summary>
    /// 定义单词符号的类型。
    /// </summary>
    internal enum TokenType
    {
        /// <summary>
        /// 操作符
        /// </summary>
        Operators,        /// <summary>
        /// 数字
        /// </summary>
        Num,        /// <summary>
        /// 左括号'('
        /// </summary>
        LeftParentheses,        /// <summary>
        /// 右括号')'
        /// </summary>
        RightParentheses,
        /// <summary>
        /// 空
        /// </summary>
        Empty
    }
}

Answer 4

变量与函数扩展只需要在TokenType 定义相应类型并在文法中定义相应的表达就可以了

Answer 5

http://www.cnblogs.com/michaelhuwei/archive/2007/12/29/1019658.html这个也能作为面试题？
明显是把项目拿来让面试者免费做啊