表达式求值、表达式转二叉树

1、后序表达式求值：

后续表达式(逆波兰式)的特点：没有括号。

求值方法：

从前向后扫，

遇到操作数压栈；

遇到操作符，从栈中取出2个操作数运算，结果压栈。

最终栈中所剩的数为结果。

2、中序表达式求值
我们先来定义运算符的优先级：
(
+,-
*,/,%
从上到下依次升高
准备2个栈，一个专门存放运算符，另一个专门存放操作数。
1.遇到)，那么退栈计算到(为止.结果压栈。
2.遇到运算数.那么压栈。
3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈.
4.否则压栈.

计算带括号和浮点数的表达式：

#include<iostream>
#include<stack>
#include<string>
#include<cctype>
using namespace std;    

typedef string::size_type it;    

char Compare(char op,char ch)    //优先级比较
{
    if((op=='#'&&ch=='#')||(op=='('&&ch==')')) return '=';
    if(ch=='#') return '<';
    if(op=='#') return '>';
    if(op=='(') return '>';
    if(ch==')') return '<';
    if(ch=='(') return '>';
    if(ch=='*'||ch=='/')
    if(op=='+'||op=='-') return '>';
    else return '<';
    if(ch=='+'||ch=='-') return '<';
}    

void modify(string& s)   //优化表达式
{
    string s1="()+-*/";
    for(it i=0;i<s.size();++i)
    {
        if(isspace(s[i])) s.erase(i,1);
        if(!isdigit(s[i])&&s[i]!='.'&&s1.find(s[i])==string::npos) s.erase(i,1);
        if(s[i]=='('&&s[i+1]=='-') s.insert(i+1,"0");
        if(i==0&&s[i]=='-') s.insert(i,"0");
    }
}    

bool check(const string & s)    //检验输入表达式
{
    string s1="()+-*/";
    string s2="+-*/";
    stack<char> ch;
    bool valid=true;
    for(it i=0;i<s.size();++i)
    {
        if(i==0 && s1.find(s[i],1)!=string::npos) return false;
        switch(s[i])
        {
        case '(':
            if(s1.find(s[i+1],1)!=string::npos) return false; break;
        case ')':
            if(s2.find(s[i-1])!=string::npos) return false; break;
        case '+':
        case '-':
        case '*':
        case '/':
            if(s2.find(s[i+1])!=string::npos) return false; break;
        }
        if (s[i]=='(') ch.push(s[i]);
        if (s[i]==')')
            if (ch.empty())
            {
                valid=false;
                break;
            }
            else
            {
                char b=ch.top(); ch.pop();
                if (b=='(') valid=true;
                else valid=false;
            }
    }
    if (!ch.empty()) valid=false;
    return valid;
}    

void Calculate(stack<double>& num,stack<char>& ops,const string & s)
{
    string s1="()+-*/#";
    it i=0;
    while(i<s.size())
    {
        it j=s.find_first_of(s1,i);
        if(j!=string::npos)
        {
            if(j!=i)
            {
                string s2=s.substr(i,j-i);
                double n=atof(s2.c_str());
                num.push(n);
            }
            char ch=s[j];
            char op=ops.top();
            if(Compare(op,ch)=='>') ops.push(ch);
            else if(Compare(op,ch)=='=') ops.pop();
            else
            {
                while(1)
                {
                    char c=ops.top();
                    if(Compare(c,ch)=='>') { ops.push(ch); break; }
                    else if(Compare(c,ch)=='=') { ops.pop(); break; }
                    else
                    {
                        char optr=ops.top();
                        ops.pop();
                        double n1=num.top();
                        num.pop();
                        double n2=num.top();
                        num.pop();
                        double value;
                        if(optr=='+') value=n2+n1;
                        if(optr=='-') value=n2-n1;
                        if(optr=='*') value=n2*n1;
                        if(optr=='/')
                        {
                            double E=0.00001;
                            if( n1>-E && n1<E )
                            {
                                cout<<"Can't evaluate the expression !";
                                exit(1);
                            }
                            else value=n2/n1;
                        }
                        num.push(value);
                    }
                }
            }
        }
        i=j+1;  //更新i的值
    }
}
int main()
{
    stack <double> num;
    stack <char> ops;
    ops.push('#');
    string s;  

    cout<<"Input the string:"<<endl;
    getline(cin,s);
    modify(s);
    while(!check(s))
    {
        cout<<"The string is not valid. Input it again! "<<endl;
        getline(cin,s);
        modify(s);
    }
    cout<<s<<endl;
    s=s+"#";    

    Calculate(num,ops,s);
    cout<<"The result is "<<num.top();    

    return 0;
}   

将中序表达式转换成后序表达式（逆波兰表达式）的算法：
(1)初始化一个空的运算符栈
(2)在没有到达中缀表达式的结尾及没有发生错误的时候，执行以下步骤：
 1.获取表达式中的一个标记（常数、变量、算术运算符，左括号，右括号）。
 2.如果标记是：
   i.  一个左括号，将其压入栈中
   ii. 一个右括号，连续弹出并显示栈中的元素，直到遇到一个左括号，不要显示这个左括号。（如果直到栈为空还没遇到一个左括号，则是一个错误）
   iii.一个运算符，如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其压入栈中。否则出并显示栈顶的元素，接着继续比较标记和新的栈顶元素。（运算符比左括号的优先级高）
   iv 一个操作数，显示它
(3)当到达中缀表达式的结尾时，弹出并显示栈中的元素直到栈为空为止。

参考代码：

//将表达式转化为逆波兰表达式
string RPN(const string& exp)
{
    char token,toptoken;
    stack<char> oper;
    string RPNexp;
    int length=exp.length();
    for(int i=0;i<length;++i)
    {
        token=exp[i];
        switch(token)
        {
        case' ': break;
        case'(':
            oper.push(token);
            break;
        case')':
            while(1)
            {
                assert(!oper.empty());
                toptoken=oper.top(); oper.pop();
                if(toptoken=='(') break;
                RPNexp+=toptoken;
            }
            break;
        case'+':
        case'-':
        case'*':
        case'/':
            while(1)
            {
                if(oper.empty()||oper.top()=='('||
                    (token=='*'||token=='/')&&(oper.top()=='+'||oper.top()=='-'))
                {
                    oper.push(token);
                    break;
                }
                else
                {
                    toptoken=oper.top();
                    oper.pop();
                    RPNexp+=toptoken;
                }
            }
            break;
        default:RPNexp+=token;
        }
    }
    while(1)
    {
        if(oper.empty()) break;
        toptoken=oper.top();
        oper.pop();
        if(toptoken!='(')
            RPNexp+=toptoken;
        else
        {
            cout<<"***Error in infix expression!***\n";
            break;
        }
    }
    return RPNexp;
}    

//计算逆波兰表达式的值
int calculate(const string& exp)
{
    string s="+-*/";
    stack<int> num;
    int num1,num2,value;
    int length=exp.length();
    for(int i=0;i<length;++i)
    {
        if(s.find(exp[i])==string::npos) num.push(exp[i]-48);
        else
        {
            if(num.size()<2)
            {
                cout<<"Error in infix expression!\n";
                exit(0);
            }
            num1=num.top(); num.pop();
            num2=num.top(); num.pop();
            if(exp[i]=='+') value=num2+num1;
            if(exp[i]=='-') value=num2-num1;
            if(exp[i]=='*') value=num2*num1;
            if(exp[i]=='/')
            {
                if(num1==0)
                {
                    cout<<"Can't evaluate the expression !";
                    exit(1);
                }
                else value=num2/num1;
            }
            num.push(value);
        }
    }
    return num.top();
}    

字符串表达式转化为二叉树：

//表达式转二叉树的源代码
#include<iostream>
#include<stack>
#include<string>
using namespace std;  

class Node
{
public:
    char oper;//操作数或运算符
    Node *left;//左子树
    Node *right;//右子树
    Node():left(NULL),right(NULL),oper(0){}
    Node(char op):left(NULL),right(NULL),oper(op){}
};  

//判断是否为运算符
bool isOper(char op)
{
    char oper[]={'(',')','+','-','*','/'};
    for(int i=0;i<strlen(oper);i++)
    {
        if(op==oper[i])
            return true;
    }
    return false;
}  

//求运算符的优先级
int getOperPri(char op)
{
    switch(op)
    {
        case '(':
        return 1; break;
        case '+':
        case '-':
        return 2; break;
        case '*':
        case '/':
        return 3; break;
        default:
        return 0;
    }
}  

//销毁二叉树
void freeTree(Node*& p)
{
    if(p->left != NULL)
        freeTree(p->left);
    if(p->right != NULL)
        freeTree(p->right);
    delete(p);
}  

//递归先序遍历
void preOrderTraverse(Node *p)
{
   if(p!=NULL)
   {
       cout<<p->oper;
       preOrderTraverse(p->left);
       preOrderTraverse(p->right);
   }
}  

//中序遍历
void inOrderTraverse(Node *p)
{
    if(p)
    {
        if(p->left)
        {
            if(isOper(p->left->oper)&&getOperPri(p->left->oper)<getOperPri(p->oper))
            {
                cout<<"(";
                inOrderTraverse(p->left);
                cout<<")";
            }
            else
            inOrderTraverse(p->left);
        }
        cout<<p->oper;
        if(p->right)
        {
            if(isOper(p->right->oper)&&getOperPri(p->right->oper)<=getOperPri(p->oper))
            {
                cout<<"(";
                inOrderTraverse(p->right);
                cout<<")";
            }
            else
            inOrderTraverse(p->right);
        }
    }
}  

//表达式生成二叉树
void generateTree(Node*& p, string expr)
{
    stack <char> operStack;
    stack <Node*> dataStack;
    char tmpchr,c;
    int idx=0;
    tmpchr=expr[idx++];
    while(operStack.size()!=0 || tmpchr!='\0')
    {
        if(tmpchr!='\0' && !isOper(tmpchr))//不是运算符，则进操作数的栈
        {
            p=new Node(tmpchr);
            dataStack.push(p);
            tmpchr=expr[idx++];
        }
        else
        {
            switch(tmpchr)
            {
            case '('://进栈
                operStack.push('(');
                tmpchr=expr[idx++];
                break;
            case ')'://脱括号
                while(true)
                {
                    c=operStack.top();
                    operStack.pop();
                    if(c=='(')
                    {
                        break;
                    }
                    p=new Node(c);
                    if(dataStack.size())
                    {
                        p->right=dataStack.top();
                        dataStack.pop();
                    }
                    if(dataStack.size())
                    {
                        p->left=dataStack.top();
                        dataStack.pop();
                    }
                    dataStack.push(p);
                }
                tmpchr=expr[idx++];
                break;
            default:
                if(operStack.size()==0 || tmpchr!='\0' && getOperPri(operStack.top())< getOperPri(tmpchr))
                {//进栈
                    operStack.push(tmpchr);
                    tmpchr=expr[idx++];
                }
                else
                {//出栈
                    p=new Node(operStack.top());
                    p->oper=operStack.top();
                    if(dataStack.size())
                    {
                        p->right=dataStack.top();
                        dataStack.pop();
                    }
                    if(dataStack.size())
                    {
                        p->left=dataStack.top();
                        dataStack.pop();
                    }
                    dataStack.push(p);
                    operStack.pop();
                }
                break;
            }
        }
    }
    p=dataStack.top();
    dataStack.pop();
}  

int main()
{
   string expression;
   Node* tree;  

   cout<<"请输入字符串表达式:";
   cin>>expression;
   generateTree(tree,expression);  

   cout<<"前缀表达式为:";
   preOrderTraverse(tree);
   cout<<endl;  

   cout<<"中缀表达式为:";
   inOrderTraverse(tree);
   cout<<endl;  

   freeTree(tree);
   cout<<endl;  

   return 0;
}  

作者：阿凡卢

出处：http://www.cnblogs.com/luxiaoxun/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

http://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622800.html