返回顶部

收藏

堆栈 四则运算 括号处理

更多

1、 输入一个数学表达式(假定表达式输入格式合法),计算表达式结果并输出。

2、 数学表达式由单个数字和运算符"+"、"-"、"*"、"/"、"(、) "构成,例如 2 + 3 * ( 4 + 5 ) - 6 / 4。

//============================================================================
// Name        : test04_201100300097.cpp
// Compiler    : MinGCC
// Language    : C/C++
// Description : test03_201100300097 in C++, Ansi-style
//============================================================================

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

int Level(char m){//算符号优先级
    switch (m){
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2; 
    case '(':
    case ')':
        return 0;
    case '#':    
        return -1;
    default:
        break;
    }
}

int main(){
    stack<char>y;
    stack<int>x;
    string s=" ";
    string ss;
    string l=" ";
    cout<<"Input"<<endl;
    cin>>s;
    ss=s;
    s+="#$";//#将y中的运算符都拿出来,$用于表示算式结尾
    int i=0;
    double c=0;
    bool m=1;
    while(s[i]!='$')
    {    
        //put number into stack
        if(s[i]>47&&s[i]<58){//the char 0-9 of ASCII is 47-58
            l+=s[i];
            for(int j=i+1;s[j]>47&&s[j]<58;j++)
                l+=s[j];
            x.push(atoi(l.c_str())); 
            l=" ";
            i=j;
        }

        if(s[i]>=35&&s[i]<=47){

            if(y.size()==0||s[i]=='('||Level(s[i])>Level(y.top()))
                y.push(s[i]);

            else{
                if(s[i]==')'){//遇到')'的情况,直接将y中的符号一个一个拿出来运算,直到//遇到'('为止
                    for(;y.top()!='(';y.pop()){
                        char d=y.top();     
                        double a=x.top();       
                        x.pop();
                        double b=x.top();
                        x.pop();
                        switch(d){
                        case '+':{
                            c=a+b;
                            break;
}
                        case '-':{
                            c=b-a;
                            break;}
                        case '*':{
                            c=a*b;
                            break;}
                        case '/':{
                            c=b/a;
                            break;}
                        default:
                            break;
                        }
                        x.push(c);          
                    }
                    y.pop();            
                }
                else{                      //遇到+,-,*,/的处理
                    for(;y.size()!=0&&Level(s[i])<=Level(y.top());y.pop()){{

                            char d=y.top();
                            int a=x.top();
                            x.pop();
                            int b=x.top();
                            x.pop();
                            switch(d){
                            case '+':{
                                c=a+b;
                                break;}
                            case '-':{
                                c=b-a;
                                break;}
                            case '*':{
                                c=a*b;
                                break;}
                            case '/':{
                                c=b/a;
                                break;}
                            default:
                                break;
                            }//end of switch
                            x.push(c);

                        }//end of if 
                    }//end of for
                    y.push(s[i]);
                }
            }//end of else*/
            i++;
        }
        else{
            cout<<"Expression"<<s[i]<<"is a wrong matter!";
            m=0;
            break;
        }
    }//end of while
    if(m)
        cout<<"Output"<<endl;
        cout<<x.top()<<endl;
        cout<<"End"<<endl;

        return 0;

}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2013-07-25 21:20:53二叉树深度优先遍历说明和c++的实现 by 玉开Sir
  2. 2014-02-05 13:32:07C++算法之图的结构 by walker30
  3. 2014-02-16 18:20:02C++解决八皇后问题 by aiheng1988
  4. 2014-03-05 16:11:07C++挑选一组数中最大的N个数 by niutao.linux
  5. 2014-05-13 19:31:43排序算法 by 蟋蟀哥
  6. 2014-05-14 18:05:23递归方法实现全排列 by 童学芬
  7. 2014-05-22 12:36:50单链表的各种操作 by 千万不要郁闷
  8. 2014-05-28 14:39:00C++算法之线性队列 by 小项
  9. 2014-06-30 20:50:04线性表 by lucasli
  10. 2014-07-10 10:49:57快速排序 [C遮言泛型版] by sxgkwei
  11. 2014-08-08 12:12:47sudoku求解数独 by aiheng1988
相关聚客文章
  1. dianlujitao 发表 2014-10-17 13:32:08 POJ 2339 Rock, Scissors, Paper
  2. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  3. dianlujitao 发表 2014-10-17 13:42:33 POJ 3844 Divisible Subsequences
  4. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  5. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  6. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  7. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  8. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  9. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  10. espace 发表 2015-07-18 17:43:14 Two Sum
  11. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  12. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation

发表评论