数据结构题目，四则运算

Question

用户从键盘输入一个计算表达式,用栈实现四则运算。表达式中含有数字,加减乘除,小括号。输出表达式的结果。用c语言实现

Answer 1

一年前我自己写的，稍微改改就能用
/***********************************
Coded by LC 2014/11/8 20:00

---

• This is our last edition,and we * *changed some details from the book Later we studied some knowledge of STL template,and the effect is * * very good. * * * * * * * * * * * * **********************************/

#include"iostream"
#include"cstdlib"
#include"cmath"
#include"string"
#include"vector"

using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define LENTH " "

template

class stack
{
private:
T base;
T *top;
int stack_size;
public:
stack(void)
{
this->base = new T[STACK_INIT_SIZE];
if (!this->base)
puts("init_stack error_1"),exit(0);
this->top = this->base;
this->stack_size = STACK_INIT_SIZE;
}
~stack(void)
{}
T get_top(void)
{
if (this->top == this->base)
puts("get_top error"), exit(0);
return *(this->top - 1);
}
void push(T e)
{
if (this->top - this->base >= this->stack_size)
{
this->base = (T)realloc(this->base, (this->stack_size + STACKINCREMENT)*sizeof(T));
if(!this->base)
puts("push error"), exit(0);
this->top=this->base+this->stack_size;
this->stack_size+=STACKINCREMENT;
}
*(this->top++)=e;
}
T pop(void)
{
if(this->top==this->base)
puts("pop error"), exit(0);
return *(--(this->top));
}
};

void suffixion(string ,string &);
double calculate(string &);
char judge(char ,char );
bool is_binary_operator(char);
double calculate(string &);
double compute(double ,char ,double );
double compute(double ,char );

int main()
{
string infix;
string suffix=LENTH;
cout<<"Please input your infix expression(End with '='):"< cin>>infix;
suffixion(infix,suffix);
cout<<"The suffix expression is:"<<suffix<<endl;
cout<<"The result is:"<<calculate(suffix)<<endl;
system("pause");
return 0;
}

void suffixion(string infix,string & suffix)
{
stack char_stack;
char_stack.push('=');
int j=0;
for(int i=0;infix[i]!='=';i++)
{
if(infix[i]>='0'&&infix[i]<='9')
{
suffix[j]=' ';
j++;
while(infix[i]>='0'&&infix[i]<='9'||infix[i]=='.')
{
suffix[j]=infix[i];
j++;
if(infix[i+1]>='0'&&infix[i+1]<='9'||infix[i+1]=='.')
i++;
else
break;
}
suffix[j]=' ';
j++;
}
else if(infix[i]=='(')
{
char_stack.push('(');
}
else if(infix[i]==')')
{
while(char_stack.get_top()!='(')
{
suffix[j]=char_stack.pop();
j++;
}
char_stack.pop();
}
else if(infix[i]>='a'&&infix[i]<='z')
{
int flag;
switch(infix[i])
{
case 'c':case's':
{
//char_stack.push(infix[i]);
flag=2;
}break;
case 'l':
{
if(infix[i+1]=='n')
{
// char_stack.push('n');
i+=1;
flag=0;
}
else if(infix[i+1]=='o')
{
// char_stack.push('l');
flag=2;
}
}break;
default: break;
}
switch(judge(char_stack.get_top(),infix[i]))
{
case '>':
{
while(judge(char_stack.get_top(),infix[i])=='>')
{
suffix[j]=char_stack.pop();
j++;
}
char_stack.push(infix[i]);
}
break;

            case '=':
            {
                char_stack.pop();
            }
            break;

            case '<':
            {
                char_stack.push(infix[i]);
            }
            break;

            default: break;
        }
        i+=flag;
    }
    else if(is_binary_operator(infix[i]))
    { 
        switch(judge(char_stack.get_top(),infix[i]))
        {
            case '>':
            {
                while(judge(char_stack.get_top(),infix[i])=='>')
                {
                    suffix[j]=char_stack.pop();
                    j++;
                }
                char_stack.push(infix[i]);
            }
            break;

            case '=':
            {
                char_stack.pop();
            }
            break;

            case '<':
            {
                //cout<<endl<<"push_isok=1"<<endl;
                char_stack.push(infix[i]);
            }
            break;

            default: break;
        }
    }
}

while(char_stack.get_top()!='=')//last , infix[i]='\0'
{
    suffix[j]=char_stack.pop();
    j++;
}
char_stack.pop();
suffix[j]='\0';

}

double calculate(string & suffix)
{
int i=0;
double a,b,n,k=0.1;
int dot_flag=0,push_flag=0;
stack num_stack;
for(int i=0;suffix[i]!='\0';i++)
{
n=0;
push_flag=0;
dot_flag=0;
k=0.1;
while((suffix[i]>='0'&&suffix[i]<='9')||suffix[i]=='.')
{
push_flag=1;
if(suffix[i]=='.')
dot_flag=1;
else
{
if(dot_flag==0)
n=n*10+(suffix[i]-'0');
else
{
n=n+(suffix[i]-'0')*k;
k/=10;
}
}
if((suffix[i+1]>='0'&&suffix[i+1]<='9')||suffix[i++]=='.')
i++;
}
if(push_flag==1)
num_stack.push(n);
if(is_binary_operator(suffix[i]))
{
b=num_stack.pop();
a=num_stack.pop();
// cout< num_stack.push(compute(a,suffix[i],b));
}
else if(suffix[i]>='a'&&suffix[i]<='z')
{
a=num_stack.pop();
// cout<<endl<<"computing："<<suffix[i]<<a<<endl;
num_stack.push(compute(a,suffix[i]));
}
}
return num_stack.get_top();
}

char judge(char a,char b)
{
int m,n;
if(a=='(' && b==')') return '=';
else
{
switch(a)
{
case '(':case '=':m=0;break;
case '+':case '-':m=1;break;
case '*':case '/':m=2;break;
case '^':case 'c':case 's':case 'l':case 'n':m=3;break;
default : break;
}
switch(b)
{
case '=':case ')':n=0;break;
case '+':case '-':n=1;break;
case '*':case '/':n=2;break;
case '^':case 'c':case 's':case 'l':case 'n':n=3;break;
case '(':n=4;break;
default : break;
}
if(m return ' else
return '>';
}
}

bool is_binary_operator(char e)
{
return (e=='+'||e=='-'||e=='*'||e=='/'||e=='^');
}

double compute(double a,char operate,double b)
{
switch(operate)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
case '^':return pow(a,b);
default : break;
}
}

double compute(double a,char operate)
{
switch(operate)
{
case 'c':return cos(a);
case 's':return sin(a);
case 'l':return log10(a);
case 'n':return log(a);
default : break;
}
}