【NYOJ35】 表达式求值 (后缀法求解)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 07 日

表达式求值的经典算法
编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年。
Knuth 将此概括为三个步骤:
1、对中缀表达式进行语法分析
2、中缀表达式到后缀表达式的转换
3、对后缀表达式求值
注意到我们谈到的这个经典算法有些简化:算术表达式只包含操作数、二元操作符和一种括号。
此外,对于每个操作数和操作符,只用单个字符表示,使语法分析直观。
表达式表示法:
算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。
中缀表示法是书写表达式的常见方式,而前缀和后缀表示法主要用于计算机科学领域。
中缀表示法:
中缀表示法是算术表达式的常规表示法。称它为中缀表示法是因为每个操作符都位于
其操作数的中间,这种表示法只适用于操作符恰好对应两个操作数的时候
(在操作符是二元操作符如加、减、乘、除以及取模的情况下)。
对以中缀表示法书写的表达式进行语法分析时,需要用括号和优先规则排除多义性。
Syntax: operand1 operator operand2
Example: (A+B)*C-D/(E+F)
前缀表示法
前缀表示法中,操作符写在操作数的前面。这种表示法经常用于计算机科学,
特别是编译器设计方面。为纪念其发明家 ― Jan Lukasiewicz,
这种表示法也称 波兰表示法。
Syntax : operator operand1 operand2
Example : -*+ABC/D+EF
后缀表示法
在后缀表示法中,操作符位于操作数后面。后缀表示法也称 逆波兰表示法
(reverse Polish notation,RPN),因其使表达式求值变得轻松,所以被普遍使用。
Syntax : operand1 operand2 operator
Example : AB+C*DEF+/-
前缀和后缀表示法有三项公共特征:
操作数的顺序与等价的中缀表达式中操作数的顺序一致
不需要括号
操作符的优先级不相关
中缀转化为后缀算法:

a. 得到一操作符或操作数;
b. 若输入为操作数,则输出到数组,转a;
c. 若输入为‘(’,压栈,转a;
d. 若输入为‘)’,栈顶出栈,输出到数组,直至栈顶为‘(’,不输出到数组(抛弃),转a;
e. 若输入为操作符,
若栈空或栈顶为‘(’或操作符.忧先级大于栈顶操作符,压栈,转a
若操作符优先级小于栈顶操作符,则出栈,输出至数组,转e;
d. 若输入结束,出栈,输出到数组,直至栈空。
数组SNode中即为后缀表达式;

优先级可以根据需要分为 栈内优先级和栈外优先级
后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中,不需要括号,
而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值:初始化一个空堆栈
从左到右读入后缀表达式,如果字符是一个操作数,把它压入堆栈。如果字符是个操作符,
弹出两个操作数,执行恰当操作,然后把结果压入堆栈。如果您不能够弹出两个操作数,
后缀表达式的语法就不正确。到后缀表达式末尾,从堆栈中弹出结果。若后缀表达式格式正确,
那么堆栈应该为空。

#include<iostream>  
#include<string>  
#include<cstring>  
#include<stack>  
#include <iomanip>  
using namespace std;  
struct oper  
{  
    double d;  
    char opera;  
};  
int judgeoper(char ch)  
{  
    int res=0;  
    switch(ch)  
    {  
        case '+': res=1; break;  
        case '-': res=2; break;  
        case '*': res=5; break;  
        case '/': res=6; break;  
        case '(': res=9; break;  
        case ')': res=10; break;  
        default:res=13;  
    }  
    return res;  
}  
int main()  
{  
    freopen("1.txt","r",stdin);  
    int n;  
    oper op;  
    char str[1005];  
    oper suffix[1005];  
    int sufp;  
    stack<oper> stac;  
    cin>>n;  
    while(n--)  
    {  
        memset(suffix,0,sizeof(suffix));  
        sufp=0;  
        cin>>str;  
        //中缀转化后缀  
        int getc=0,len=strlen(str);  
        while(getc<len-1)  
        {  
            if(judgeoper(str[getc])==13)  
            {  
                sscanf(str+getc,"%lf",&op.d);  
                op.opera='R';  
                while(1)  
                    if(judgeoper(str[++getc])!=13) break;  
            }  
            else  
            {  
                sscanf(str+getc,"%c",&op.opera);  
                op.d=0;  
                getc++;  
            }  
            char temp=op.opera;  
            switch(judgeoper(temp))  
            {  
                case 13:suffix[sufp++]=op;break;  
                case 9:stac.push(op);break;  
                case 10:  
                    while(stac.top().opera!='(')  
                    {  
                        suffix[sufp++]=stac.top();  
                        stac.pop();  
                    }  
                    stac.pop();  
                    break;  
                default:  
                    while(1)  
                    {  
                        if(stac.empty() || (stac.top().opera=='(')   
                            || (judgeoper(temp)-judgeoper(stac.top().opera)>=3))  
                        {  
                            stac.push(op);  
                            break;  
                        }  
                        else  
                        {  
                            suffix[sufp++]=stac.top();  
                            stac.pop();  
                        }  
                    }  
            }  
        }  
        while(!stac.empty())  
        {  
            suffix[sufp++]=stac.top();  
            stac.pop();  
        }  
        //后缀法计算  
        int res=0;  
        stack<double> stadou;  
        while(res<sufp)  
        {  
            if(suffix[res].opera=='R')  
                stadou.push(suffix[res].d);  
            else  
            {  
                double t1=stadou.top();  
                stadou.pop();  
                double t2=stadou.top();  
                stadou.pop();  
                switch(judgeoper(suffix[res].opera))  
                {  
                    case 1:stadou.push(t2+t1); break;  
                    case 2:stadou.push(t2-t1); break;  
                    case 5:stadou.push(t2*t1); break;  
                    case 6:stadou.push(t2/t1); break;  
                }  
            }  
            res++;  
        }  
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<stadou.top()<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日