逆波兰表达式 - dblank

逆波兰表达式

<div>表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,</div>
<div>这称为中缀表达式(Infix Expression),如A+B。</div>
<div>波兰数学家Jan Lukasiewicz提出了另一种数学表示法,它有两种表示形式:</div>
<div>把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;</div>
<div>把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+;</div>
<div>其中,逆波兰表达式在编译技术中有着普遍的应用。</div>
<div>比如 1 + 2 3  + 2 ( 1 + 3)这个是一个中缀表达式,转换为后缀表达式为1 2 3 2 1 3 + + +</div>
<div>算法:</div>
<div>(1).将一个中缀表达式转换为一个后缀表达式。</div>
<div>          1.定义一个栈结构in,和后缀表达式s。</div>
<div>          2.从左往右扫描整个中缀表达式,遇到数字的话直接加到表达式s后面。</div>
<div>          3.遇到运算符,如果栈in为空,则直接加入到栈in,不为空的话,如果栈顶运算符的优先级比这个运算符的优先级一样高或者更高,则将栈顶元素出栈并加入到表达式s,进行这个操作直到栈顶元素优先级比这个运算符低或者栈为空。</div>
<div>          4.遇到左括号'(‘,直接加入到栈in里面。</div>
<div>          5.遇到右括号')'把栈顶出栈到表达式s,直到遇到左括号,这个左右括号都出栈并且不加入到表达式里面。</div>
<div>          6.中缀表达式遍历结束后,将栈全部出栈,加入的表达式s。</div>
<div>(2)得到后缀表达式后,定义一个栈out,遍历后缀表达式,如果是数字则加入到栈out,遇到运算符则运算栈out的栈顶相应个数的数字,并把这些数字出栈,并且把运算结果加入到栈out,最后栈中会剩余一个元素,这个元素即为中缀表达式的结果。</div>
<div>后缀表达式可以很好的被计算机运算,而中缀表达式虽然我们人可以很好的计算,但计算机却不行。</div>
<div>中缀表达式计算实现代码:</div>
<div>

#include<bits/stdc++.h>
using namespace std;
int Grade(char c)
{
    if(c == '*' || c == '/' || c == '%')
        return 2;
    else if(c == '+' || c == '-')
        return 1;
}
int main()
{
    char Infix_expression[1000];
    while(gets(Infix_expression))
    {
        int sz = strlen(Infix_expression);
        string Postfix_Expression = "", plc = "";
        stack<char>sta;
        for(int i = 0; i<sz; i++)
        {
            if(Infix_expression[i] == ' ')
                continue;
            if(isdigit(Infix_expression[i]))
                Postfix_Expression = Postfix_Expression + Infix_expression[i];
            else if(Infix_expression[i] != ')')
            {
                if(Infix_expression[i] == '(' || sta.empty())
                {
                    sta.push(Infix_expression[i]);
                }
                else
                {
                    while(!sta.empty() && Grade(sta.top()) > Grade(Infix_expression[i])
                          && sta.top()!= '(')
                    {
                        Postfix_Expression = Postfix_Expression + sta.top();
                        sta.pop();
                    }
                    sta.push(Infix_expression[i]);
                }
            }
            else if(Infix_expression[i] == ')')
            {
                while(!sta.empty() && sta.top() != '(')
                {
                    Postfix_Expression = Postfix_Expression + sta.top();
                    sta.pop();
                }
                sta.pop();
            }
        }
        while(!sta.empty())
        {
            Postfix_Expression = Postfix_Expression + sta.top();
            sta.pop();
        }
        cout<<Postfix_Expression<<endl;
        stack<int>ans;
        for(int i = 0; i<Postfix_Expression.size(); i++)
        {
            if(isdigit(Postfix_Expression[i]))
                ans.push(Postfix_Expression[i] - '0');
            else
            {
                int a = ans.top();
                ans.pop();
                int b = ans.top();
                ans.pop();
                if(Postfix_Expression[i] == '+')
                    ans.push(a+b);
                if(Postfix_Expression[i] == '-')
                    ans.push(b-a);
                if(Postfix_Expression[i] == '*')
                    ans.push(a*b);
                if(Postfix_Expression[i] == '/')
                    ans.push(b/a);
            }
        }
        cout<<ans.top()<<endl;
    }
    return 0;
}

</div>

发表新评论