posts - 21,  comments - 9,  trackbacks - 0
今天刷刷我们学校的OJ。看到了那道我们大家都熟悉的表达式求值题目。去网上搜了下,发现没有现成可用的好的算法。于是自己花了点时间写了个。没有做过多优化,先发出来再说。
  1#include<stdio.h>
  2#include<string.h>
  3#include<stack>
  4using namespace std;
  5
  6char exp[1100];
  7char num[100];//此数组用来把字符数字转化为整数
  8
  9stack<char> cstack;
 10stack<double> nstack;
 11
 12int n;
 13
 14int convert(int length)
 15{
 16    int value = 0;
 17    for(int i = 0;i < length;++i)
 18    {
 19        value = value * 10 + num[i]-'0';
 20    }

 21    return value;
 22}

 23
 24//判断a运算符比b优先。如果是的话,那么返回1如果不是的话,返回0
 25int order(char a ,char b)
 26{
 27    if(a == '*' || a == '/')
 28    {
 29        return 1;
 30    }

 31    if(a == '+' || a == '-')
 32    {
 33        if(b == '*' || b== '/')
 34            return 0;
 35        else
 36            return 1;
 37    }

 38    return 0;
 39}

 40
 41//这个函数用来判断字符是数字还是运算符
 42
 43int judge(char c)
 44{
 45    if(c <= '9' && c >= '0')
 46        return 1;
 47    else
 48        return 0;
 49}

 50
 51
 52double go(char c,double n1,double n2)
 53{
 54    if(c == '+')
 55        return n1 + n2;
 56    else
 57        if(c == '-')
 58            return n1 - n2;
 59    else
 60        if(c == '*')
 61            return n1 * n2;
 62    else
 63        if(c == '/')
 64            return n1 / n2;
 65    return 0;
 66}

 67
 68int ignoreKuohao(stack<char> &ccstack,stack<double>& nnstack)
 69{
 70    while(!ccstack.empty() && ccstack.top()!='(')
 71    {
 72        char c1 = ccstack.top(); ccstack.pop();
 73        double n1 = nnstack.top();    nnstack.pop();
 74        double n2 = nnstack.top();    nnstack.pop();
 75        if(ccstack.empty())
 76        {
 77            nnstack.push(go(c1,n1,n2));
 78            break;
 79        }

 80        else
 81        {
 82            char c2 = ccstack.top(); ccstack.pop();
 83            if(order(c1,c2))
 84            {
 85                double k = go(c1,n1,n2);
 86                ccstack.push(c2);
 87                nnstack.push(k);
 88            }

 89            else
 90            {
 91                //nnstack.push(n1);
 92                double n3 = nnstack.top();nnstack.pop();
 93                double k = go(c2,n2,n3);
 94                nnstack.push(k);
 95
 96                k = nnstack.top();
 97                nnstack.push(n1);
 98
 99                k = nnstack.top();
100                ccstack.push(c1);
101            }

102        }

103    }

104    if(!ccstack.empty() && ccstack.top() == '(')
105    {
106        ccstack.pop();
107    }

108
109    return 0;
110}

111
112
113
114//事实证明,在没有括号的情况下,应该从前往后进行计算
115void inKuohao()
116{
117    char c = cstack.top();
118    stack<char> ccstack;
119    stack<double> nnstack;
120    //把括号内的表达式逆过来
121    int n = nstack.top();
122    nnstack.push(n);
123    nstack.pop();
124    while(c != '(')
125    {
126        cstack.pop();
127        ccstack.push(c);
128
129        nnstack.push(nstack.top());
130        nstack.pop();
131        if(cstack.empty())
132            break;
133        c = cstack.top();
134    }

135    if(!cstack.empty())
136    {
137        cstack.pop();
138    }

139    ignoreKuohao(ccstack,nnstack);
140    nstack.push(nnstack.top());
141    nnstack.pop();
142}

143
144int calc(int j)
145{
146    int i = 0;
147    int length = 0;
148//    stack<char> cstack;
149//    stack<int> nstack;
150    for(i = 0;i <= j ;++i )
151    {
152        if(judge(exp[i]))
153        {
154            num[length ++ ] = exp[i];
155        }

156        else
157        {
158            if(judge(exp[ i - 1]))//如果上一个是数字的话,就入栈.这个判断是为了防止出现(2 + 1 )/2。这种情况
159            {
160                int k = convert(length);
161                nstack.push(k);
162                length = 0;
163            }

164            if(exp[i] == ')')
165                {
166                    inKuohao();
167                }

168            else
169                if(exp[i] == '#')
170                    break;
171            else
172                cstack.push(exp[i]);
173        }

174    }

175    if(!cstack.empty())
176    {
177        inKuohao();
178    }

179    int k =(int) nstack.top();
180    printf("%d\n",k);
181    return k;
182}

183
184int main()
185{
186    scanf("%s",exp);
187    int j = strlen(exp);
188    exp[j] = '#';
189    exp[j + 1= '\0';
190    calc(j);
191    return 0;
192}

193
posted on 2011-04-24 21:00 崔佳星 阅读(265) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜