表达式翻译_按翻译模式处理表达式

一,对表达式翻译的认识:

由中缀变后缀,即由标注的算术表达式变为计算机易识别的式子,并输出结果.例:中缀为:  9+(3-1)*3+10/2   变为后缀:  9 3 1 – 3 * + 10 2 + /  计算结果为: 20

 二 ,转换的主要思想:

第一步:遇到数字9在后缀表达式中直接输出,接着是符号”+”入栈 ,

 第二步:第三个字符是“（”，依然是符号，这个时候将此符号入栈，接着是数字3，直接输出，然后是符号“-”，这个时候符号仍然入栈

第三步:接下来是数字1输出，紧跟着是“）”，此时，我们需要匹配栈里的“（”，然后再匹配前将栈顶数据依次出栈：

 第四步:紧接着是符号“*”，直接入栈：

 第五步:遇到数字3，直接输出，之后是符号“+”，此时栈顶元素是符号“*”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加号要大，所以出栈。而栈中的第二个元素是加号，按照先到先后的原则，这个时候“+”也要出栈。

 第六步:紧接着是数字10，直接输出，最后是符号“/”，进栈：

 第七步:最后一个数字5，这个时候直接输出5，但是栈里仍然有数据，此时可以将栈中符号依次出栈。

三,对后缀表达式的计算:

1. 初始化一个空栈。此桟用来对要运算的数字进出使用。

2. 后缀表达式中前三个都是数字，所以9、3、1进栈。

 

3. 接下来是减号“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。

4. 接着是数字3进栈。

 

5. 后面是乘法“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。

6. 下面是加法“+”，所以找中6和9出找，9与6相加，得到15，将15进栈。

 

7. 接着是10与2两数字进栈。

8. 接下来是符号因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。

 

9. 最后一个是符号“+”，所以15与5出找并相加，得到20，将20进栈。

10. 结果是20出栈，栈变为空。

 

四,核心代码

(1)     由前缀变后缀:

char* GetBack()//获取后缀表达式的函数
{
 
    char* middle = new char[30];
 
    char* back = new char[30];
 
    char* backend = back;
 
    InPut(middle);
 
    stack s;
 
    s.push('#');
 
    while (*middle)
 
    {
 
        if (Number(*middle) || *middle =='.')//如果是数字或者小数的话，直接输出
 
        {
 
            *back = *middle;
 
            back++, middle++;
 
        }
 
        else
 
        {
 
            if (Number(*(back - 1)))//只有他的上一个时数字的话，才继续给空格
 
                                    //否则遇到多个操作符，则输出域会存在多个空格
 
            {
 
                AddSpace(back);
 
            }
 
            if (*middle == ')')//如果右括号的话，输出所有操作符直到遇到左括号，并抛弃相对应的一堆括号
 
            {
 
                while (s.top() != '(')
 
                {
 
                    *back = s.top();
 
                    s.pop();
 
                    back++; middle++;
 
                    AddSpace(back);
 
                }
 
                s.pop();//抛弃左括号
 
            }
 
            else if (*middle == '(')//遇到左括号，则进入栈
 
            {
 
                s.push(*middle); middle++;
 
            }
 
            else if (GetPriority(*middle) >GetPriority(s.top()))//如果栈内的操作符优先级高于栈外的优先级，则入栈
 
            {
 
                s.push(*middle); middle++;
 
            }
 
            else if (GetPriority(*middle) <=GetPriority(s.top()))
 
                                            //如果栈内的操作符优先级低于或等于栈外的优先级，输出栈内的符号，并入栈栈外的符号
 
            {
 
                *back = s.top();
 
                s.pop();
 
                s.push(*middle);
 
                back++; middle++;
 
                AddSpace(back);
 
            }
 
        }
 
    }
 
    while (s.top() != '#')//中缀表达式遍历完成，但是=栈中还有符号存在，一一出栈输出
 
    {
 
        AddSpace(back);
 
        *back = s.top();
 
        s.pop(); back++;
 
    }
 
    *back = '\0';
 
    cout << "后缀表达式为: " << backend << endl;
 
    return backend;
 
}
 
(2)    后缀表达式的计算:
 
double CountBack(char*back)
 
{
 
    stack s;
 
    while (*back)
 
    {
 
        if (Number(*back))//遇到数字
 
        {
 
            s.push(GetNumber(back));//将正确的数字入栈
 
        }
 
        else if (*back == ' ')
 
        {
 
            back++;//遇到空格跳过
 
        }
 
        else
 
        {
 
            double a = s.top();
 
            s.pop();
 
            double b = s.top();
 
            s.pop();
 
            s.push(Cauculate(*back, b, a));//遇到符号时，取栈顶的第二个数和第一个数求解，并入栈
 
            back++;
 
        }
 
    }
 
    while (s.size() >= 2)//最终栈内存在的数大于2时，继续计算，直到只剩下一个数
 
    {
 
        double a = s.top();
 
        s.pop();
 
        double b = s.top();
 
        s.pop();
 
        s.push(Cauculate(*back, b, a));
 
    }
 
    //返回这个数字，既是最终结果
 
    return s.top();
 
}