表达式求值

data_structure

一、 程序思路

1. 问题分析：

表达式是由运算对象、运算符和圆括号组成的式子。在这个程序中只讨论简单的算术运算。为了实现运算符的优先运算，用两个栈分别存储表达式：
OPND：运算对象栈，用来存储运算对象和运算结果；
OPTR：运算符栈，用来存储运算符；

2. 算法思想：

规定@为表达式的定界符，输入的表达式以@为结束标志

• （1） 将栈OPND初始化为空，OPTR初始化为表达式的定界符@；

• （2） 依次读入表达式的每个字符，进行如下操作，直到读到@且OPTR栈的栈顶元素为@：

  1. 若当前字符是操作数，则进OPND栈，继续读下一个字符；
  2. 若当前字符是运算符，且比OPND的栈顶运算符的优先级高，则进OPTR栈，继续读入下一个字符；
  3. 若当前字符是运算符，且比OPND的栈顶运算符的优先级低，则从OPTR栈弹出一个运算符，从OPND栈弹出两个操作数，进行运算，并让运算结果进栈OPND，继续处理当前字符；
  4. 若当前字符是运算符，且与OPND的栈顶运算符的优先级相等，则从弹出OPTR栈的栈顶运算符，继续读入下一个字符；
• （3） 输出OPND的栈顶元素（即表达式的运算结果）。

二、代码实现：

1、用数组prcd表示各运算符之间的优先级关系

const char prcd[7][7] = {'>', '>', '<', '<', '<', '>', '>',
                       '>', '>', '<',   '<', '<', '>', '>',
                       '>', '>', '>', '>', '<', '>', '>',
                       '>', '>', '>', '>', '<', '>', '>',
                       '<', '<', '<', '<', '<', '=', ' ',   
                       '>', '>', '>', '>', ' ', '>', '>',
                       '<', '<', '<', '<', '<', ' ', '='};

2、函数PtrToInt

将运算符与它在数组中的下标相关联，使得利用数组prcd来比较栈顶运算符与当前运算符之间的优先级关系。

int PtrToInt(char c)
{
    if('+' == c)    return 0;
    if('-' == c)    return 1;
    if('*' == c)    return 2;
    if('/' == c)    return 3;
    if('(' == c)    return 4;
    if(')' == c)    return 5;
    if('@' == c)    return 6;
    else
    {
        cerr<<"输入的运算符不合法！"<<endl;
                exit(1);
    }
}

3、函数Operater

用来计算left oper right这个式子的值，并返回。

float Operater(float left, char oper, float right)
{
    switch(oper)
    {
        case '+':
            {
                return left + right;
                break;
            }
        case '-':
            {
                return left - right;
                break;
            }
        case '*':
            {
                return left * right;
                break;
            }
        case '/':
            {
                if(0 == right)
                {
                    cerr<<"除数不能为0！"<<endl;
                    exit(1);
                }
                return left / right;
                break;
            }
        default:
            {
                cerr<<"输入的运算符不合法！！"<<endl;
                exit(1);
            }
    }
}

4、函数Calculate

用来计算表达式的值，用两个栈OPND和OPTR分别存放运算对象和运算符。依次读入表达式的字符，进行操作数和运算符的判断，并进入各自的栈。根据运算符的优先级，进行计算，最后得出结果，返回表达式的值。

float Calculate ()
{
    SeqStack<float, MaxSize> OPND;          //运算对象栈
    SeqStack<char, MaxSize> OPTR;           //运算符栈
    OPTR.Push('@');                         //初始化运算符栈
    float left, right;                      //左操作数，右操作数
    char oper;                              //双目运算符
    cout<<"请输入要计算的表达式："<<endl;  
    char ch;    
    ch = getchar();
    while(ch != '@' || OPTR.GetTop() != '@')
    {
        if(ch >= '0' && ch <= '9')
        {
            OPND.Push(ch - '0');
            ch = getchar();
        }
        else
        {
            switch(prcd[PtrToInt(OPTR.GetTop())][PtrToInt(ch)])
            {
                case '<':
                    {
                        OPTR.Push(ch);
                        ch = getchar();
                        break;
                    }
                case '>':
                    {
                        oper = OPTR.Pop();
                        right = OPND.Pop();
                        left = OPND.Pop();
                        OPND.Push(Operater(left, oper, right));
                        break;
                    }
                case '=':
                    {
                        oper = OPTR.Pop();
                        ch = getchar();
                        break;
                    }
            }
        }
    }
    return OPND.GetTop();
}

5、测试结果

int main()
{
    double result = Calcu();
    cout << result << endl;
    return 0;
}

简单的案例：

错误的案例：

三、总结

基本的实现了算数操作，但有关功能还待后续版本。