表達式轉二叉樹、計算帶括号和浮點數的表達式

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;
}