【题解】C 语言数据结构之栈：中缀表达式的计算

注：本人技术不咋的，就是拿代码出来和大家看看，代码漏洞百出，完全没有优化，主要看气质，是吧

学了数据结构——栈，当然少不了习题。习题中最难的也是最有意思的就是这个中缀表达式的计算了（可以算+-*/和^，当然也可以带小括号）。搞了很久很久啊，终于搞出来的。简单说一下程序原理：

因为中缀表达式基本没法算（就算可以也肯定会超时），所以得把中缀表达式转为后缀表达式。

程序分为两步

第一步：将中缀表达式转为后缀表达式

创建一个字符串，比如叫 get，用于存储后缀表达式

先是输入一个字符串，逐一读取单个字符，当是数字则直接存入 get，如果是操作符则：

创建栈，比如叫 chas

while 循环 当栈顶操作符优先级大于或等于当前操作符则弹出并把栈顶元素赋值给 get 直到发现优先级小于当前操作符的栈顶的操作符，小于当前操作符的那个栈顶操作符不弹出 然后将当前操作符压入栈内

当当前操作符为'(‘ 则直接压入栈内

当当前操作符为’)’ 则 while 循环 弹出栈顶操作符并赋值给 get 直到弹出的是'(‘（‘(‘ 只弹出不赋值）注意，’)’ 不压入栈中

第二步：计算 get

创建 int 型数组栈，比如 ints

逐个读入 get

当读到数字压入 ints

当读到操作符则弹出两个 ints 的栈顶元素，并进行相应计算，将计算得到的值压入栈 ints 中

最后读完 get 时，ints 数组只剩下一个元素了，输出。

自个儿写的稀巴烂源码 (c):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int ints[10000];
int intt;//ints 的 top 
char chas[10000];
int chat;//chas 的 top 
int i=0, ii=1;
char c;
char get[10000];//输入的中缀表达式 
char get2[10000];//计算得出的后缀表达式 

void intpush(int x)//整型栈压栈 
{
    intt++; ints[intt]=x;
}
void chapush(char x)//字符型栈压栈 
{
    chat++; chas[chat]=x;
}
int intpop()//整型栈弹出 
{
    intt--; return ints[intt+1];
}
char chapop()//字符型栈弹出 
{
    chat--; return chas[chat+1];
}
void intadd(int x)//整型栈栈顶元素加入新的个位数字 
{
    ints[intt]*=10; ints[intt]+=x;
}

int find()//get2 加入操作符 
{
    c=chapop();
    get2[ii]=' ';
    get2[ii+1]=c;
    ii+=2;
    if(chat==0) return 0;
    return 1;
}

int main()
{
    intt=0; chat=0;
    fgets(get, 1000000, stdin);
    int lengets=strlen(get);
    for(i=0;i<=lengets-1;i++)//逐个读取输入的中缀表达式 
    {
        if (isdigit(get[i]))//当 get[i] 为数字时 
        {
            get2[ii]=get[i];
            ii++;
        }
        else
        {
            if(get[i]=='(')chapush('(');
            if(get[i]=='^')chapush('^');
            if(get[i]==')')
            {
                c=chapop();
                while(c!='(')
                {
                    get2[ii]=' ';
                    get2[ii+1]=c;
                    ii+=2;
                    c=chapop();
                }
            }
            if(get[i]=='+')
            {
                while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('+');
            }
            if(get[i]=='-')
            {
                while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('-');
            }
            if(get[i]=='*')
            {
                while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('*');
            }
            if(get[i]=='/')
            {
                while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('/');
            }
            get2[ii]=' ';
            ii++;
        }

    }
    while(chat>0)//输出栈内剩余的操作符 
    {
        int c=chapop();
        get2[ii]=' ';
        get2[ii+1]=c;
        ii+=2;
    }
    get2[ii]='@';//加入结束符 
    i=1;
    while(get2[i]!='@')//当看到结束符停止计算 
    {
        if(get2[i]=='+'||get2[i]=='-'||get2[i]=='*'||get2[i]=='/'||get2[i]=='^')
        {
            int a=intpop();int b=intpop();int c;
            if(get2[i]=='+') c=a+b;
            if(get2[i]=='-') c=b-a;
            if(get2[i]=='*') c=a*b;
            if(get2[i]=='/')
            {
                if (!a)puts("err"),exit(0);
                c=b/a;
            }
            if(get2[i]=='^') c=pow(b,a);
            intpush(c);
        }
        else
        {
            if(get2[i]!=' ')
            {
                intpush(get2[i]-48);
                ii=1;
                while(get2[i+ii]!=' ')
                {
                    intadd(get2[i+ii]-48);
                    ii++;
                }
                i+=ii-1;
            }
        }
        i++;
    }
    printf("%d\n",ints[1]);
    return 0;
}

样例输入：

1+(3+2) * (7^2+6 * 9)/(2)

样例输出：

258

好了，就写到这了。（原题：信息学奥赛一本通 C++版 数据结构 栈 上机练习 4 calc）//别问我为什么 C++的书的练习我写的是 C，我不会告诉你是因为那样文件名可以少打两个 p

对了，再说一下，其实这玩意完全没必要写这么长，最 NB 办法：

右键桌面：新建文本文件

双击打开新建文本文件.txt，输入如下脚本：

@echo off
set /p get=
set /a ans=%get%
echo %ans%
pause
exit:: 可以不要这句 exit

右键新建文本文件，重命名为：calc.bat

双击打开

样例输入：

1+(3+2) * (7 * 7+6 * 9)/(2)

样例输出：

258

除了乘方没法算，别的都一样

呵呵，我不想多说什么了……

最新更新（2016/7/4）：新代码，同样的功能，更快的速度，更短的代码

#include <stdio.h>
#include <string.h>
#include <math.h>
char ops[101];
int opsi=0;
int ovs[101];
int ovsi=0;
void opsin(char c)
{
    opsi++;
    ops[opsi]=c;
}
void ovsin(int num)
{
    ovsi++;
    ovs[ovsi]=num;
}
char opsout()
{
    opsi--;
    return ops[opsi+1];
}
int ovsout()
{
    ovsi--;
    return ovs[ovsi+1];
}
void count2(char c)
{
    int b=ovsout();
    int a=ovsout();
    switch(c)
    {
        case '+':ovsin(a+b);break;
        case '-':ovsin(a-b);break;
        case '*':ovsin(a*b);break;
        case '/':ovsin(a/b);break;
        case '^':ovsin(pow(a,b));break;
    }
}
int count(const char *str)
{
    ops[0]=0;
    int stri=0,lenstr=strlen(str);
    while(stri<=lenstr-1)
    {
        if(str[stri]=='(')opsin('(');
        else
        if(str[stri]=='^')opsin('^');
        else
        if(str[stri]==')')
        {
            char c=opsout();
            while(c!='(')
            {
                count2(c);
                c=opsout();
            }
        }
        else
        if(str[stri]=='+')
        {
            while(ops[opsi]=='+'||ops[opsi]=='-'||ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
            opsin('+');
        }
        else
        if(str[stri]=='-')
        {
            while(ops[opsi]=='+'||ops[opsi]=='-'||ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
            opsin('-');
        }
        else
        if(str[stri]=='*')
        {
            while(ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
            opsin('*');
        }
        else
        if(str[stri]=='/')
        {
            while(ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
            opsin('/');
        }
        else//num
        {
            if(stri>0)
            {
                if(str[stri-1]-48>=0&&str[stri-1]-48<=9)
                    ovsin(ovsout()*10+str[stri]-48);
                else
                    ovsin(str[stri]-48);
            }
            else
                ovsin(str[stri]-48);
        }
        stri++;
    }
    while(ovsi>1)count2(opsout());
    return ovs[1];
}
int main()
{
    char s[101];
    gets(s);
    printf("%d",count(s));
    return 0;
}