数学表达式解析的简单指南

本文献给我的爱人 Aida。

• 下载源代码 - 52.64 KB

引言

本文描述了一个实用的数学解析器 - 一个可用于执行基本算术运算的交互式程序。 实际上，为了使本文易于理解，我尽量避免任何不必要的项目，因此您不能将此程序用作真正的计算器，它仅适用于整数，并且可以解析包含 + 、 - 、 * 、 / 、 ( 、 ) 的表达式。

当我第一次开始考虑编写代码来计算数学表达式时，我很快意识到这并不容易 [至少对我而言]。 我不得不深入研究诸如解析、标记、词法分析、节点树和表等概念。

该算法的规则与我们在代数中学到的规则相同。 例如：先乘（或除）后加或减； 从内部括号开始，向外工作； 如果一对二元运算符具有相同的优先级，则首先执行该对的左侧运算符。

这是它的屏幕截图

Using the Code

这个计算器或者说数学解析器的想法是以树和节点的方式思考。 我认为下面的图片可以解释整个想法

a+b*c*(d-e)

您可以看到先乘（或除）后加或减的算法； 从内部括号开始，向外工作； 如果一对二元运算符具有相同的优先级，则首先执行该对的左侧运算符。

首先，我创建了ParseExpr()函数。 此函数将两个操作数彼此相加或相减，但在那之前，它会检查每个操作数之后是否有任何 * 或 /，因此它会调用ParseFactor()函数，该函数用于将两个操作数相乘或相除。 当然，它会检查一对括号中是否有任何表达式，因此它会调用ParseTerm()函数来检查花括号之间的那些表达式，然后在此时它到达值，因此我们应该解析它，然后它会调用ParseNumber()。

例如，首先它调用ParseExpr(Expression) -> ParseFactor(Expression) -> ParseTerm(Expression) -> ParseNumber(Expression)并返回a，然后将表达式剪切为+b*c*(d-e)，因此从ParseNumber返回的值进入op，然后检查第一个字符以查看它是否是加号，并且它是加号，因此它将表达式剪切为b*c*(d-e)，然后它重复上次的操作并组成上面的树。

代码块

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace csharpcalc
{
    class Expression
    {
        public int ParseExpr(ref string expr)
        {
            int op , op1;
            op = ParseFactor(ref expr);
            if (expr.Length != 0 )
            {
                if (expr[0] == '+')
                {
                    expr = expr.Substring(1, expr.Length - 1);
                    op1 = ParseExpr(ref expr);
                    op += op1;
                }
                else if (expr[0] == '-')
                {
                    expr = expr.Substring(1, expr.Length - 1);
                    op1 = ParseExpr(ref expr);
                    op -= op1;
                }
            }
            return op;
        }
        public int ParseFactor(ref string expr)
        {
            int op, op1;
            op = ParseTerm(ref expr);
            if (expr.Length != 0)
            {
                if (expr[0] == '*')
                {
                    expr = expr.Substring(1, expr.Length - 1);
                    op1 = ParseFactor(ref expr);
                    op *= op1;
                }
                else if (expr[0] == '/')
                {
                    expr = expr.Substring(1, expr.Length - 1);
                    op1 = ParseFactor(ref expr);
                    op /= op1;
                }
            }
            return op;
         }
        public int ParseTerm(ref string expr)
        {
            int returnValue = 0;
            if (expr.Length != 0)
            {
                if (char.IsDigit(expr[0]))
                { 
                    returnValue = ParseNumber(ref expr);
                    return returnValue;
                }
                else if (expr[0] == '(')
                {
                    expr = expr.Substring(1, expr.Length - 1);
                    returnValue = ParseExpr(ref expr);
                    return returnValue;
                }
                else if (expr[0] == ')')
                    expr = expr.Substring(1, expr.Length - 1);
            }
            return returnValue;
        }
        public int ParseNumber(ref string expr)
        {
            string numberTemp = "";
            for (int i = 0; i < expr.Length && char.IsDigit(expr[i]); i++)
            {
                if (char.IsDigit(expr[0]))
                {
                    numberTemp += expr[0];
                    expr = expr.Substring(1, expr.Length - 1);
                }
            }
            return int.Parse(numberTemp);
        }
    }
}

如果你想...

如果您想完成此项目以接受双精度数字，您可以在ParseNumber()方法中添加if块，即使char.IsDigit()是false，也要检查它是否是“.”，如果是，则将其添加到numberTemp中，然后进行转换。

如果您想向该项目添加一些其他数学函数，例如sin()、cos()等，您可以检查ParseTerm函数中表达式的第一个char以查看它是否是字母（char.IsLetter），然后调用一个像ParseWord()这样的函数，此后拆分单词，您可以使用switch case块。

关注点

我是一名控制工程师，但我一直热爱计算机编程，这个简单的项目让我过去的梦想成真。

历史

自从我16岁的时候，我就梦想着编写一个数学解析器，但我总是还有其他工作要做。 最终我决定写那个。 在搜索文献后，我遇到了 Robert M. Graham（Wiley，1975）的《系统编程原理》中用于解析算术表达式的算法提纲。