表达式求值

问题描述】

算数四则运算的规则是1）先乘除，后加减；2）从左算到右；3）先括号内，后括号外。

由此，算式4+23-10/5的计算顺序为4+23-10/5=4+6-10/5=4+6-2=8。

给定一个以“#”作为结束符的算式，求出算式的结果

【输入形式】

以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

【输出形式】

输出表达式运算的结果。

【样例输入】

4+2*3-10/5#

3*(7-2)#

2*3/2#

【样例输出】

8

15

3
【提示】

使用栈来解决本题，会使用两个栈，一个是存储运算符的，类型为char；另一个存储运算数，类型为float。而操作两个栈的函数都一样。C++中使用模板类，可以很方便的实现，C语言中就需要将这两个栈结合在一起，由于char与int有种特别的联系，可以使用int来代替char存储运算符。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
#define OK 1
#define ERROR 0
#define max 1000
using namespace std;
/*1.主函数输入三组字符串
2.读入入栈的函数：建立两个栈分别存储运算数和运算符， 
运算数就入第一个栈，
3.运算符比较优先级
如果优先级 大于栈顶运算符就压栈
如果小于或等于，将栈顶运算符和运算数的栈顶和倒数第二个数计算结果再压入栈 
*/ 
struct SeqStack1
{
	int elem[100];
	int top;
	};
	
struct SeqStack2
{
	char elem[100];
	int top;
	};
	
	void Init(SeqStack1 *S)
	{
		S->top=-1;
	}
   void Init(SeqStack2 *S)
	{
		S->top=-1;
	}
	
int Push(SeqStack1 *S,int x)
{
	if(S->top==max-1)
	return ERROR;
	S->top++;
	S->elem[S->top]=x;
	return OK;
}

int Push(SeqStack2 *S,char x)
{
	if(S->top==max-1)
	return ERROR;
	S->top++;
	S->elem[S->top]=x;
	return OK;
}



int Pop(SeqStack1 *S)
{   int x;
	if(S->top==-1)
	return ERROR;
	else
	{
		x=S->elem[S->top];
		S->top--;
		return x;
	}
}
char  Pop(SeqStack2 *S)
{   char x;
	if(S->top==-1)
	return ERROR;
	else
	{
		x=S->elem[S->top];
		S->top--;
		return x;
	}
}


int GetTop(SeqStack1 *S)
{    int x;
	if(S->top==-1)
	return ERROR;
	else
	{	
		x=S->elem[S->top];
		return x;
	}
}

char GetTop(SeqStack2 *S)
{    char x;
	if(S->top==-1)
	return ERROR;
	else
	{	
		x=S->elem[S->top];
		return x;
	}
}


char Compare(char c,char d ) //规定优先级表 ，c为当前输入，d为运算符栈顶 
{  /*优先级低返回<，把之前的算出来，
高的返回> 进栈
右括号不进栈，碰到就算
左括号直接进栈，到再读入右括号*/


if (c==')')   //如果是右括号 
     {
        if (d == '(') //上一个为左括号，括号里没有运算，返回‘=’ 
		{
            return '=';
        } 
		else {//上一个不是左括号，）不进栈，把之前的算出来 返回< 
            return '<';
        }
    }
if (c=='('||d=='(')//左括号直接进栈 
        return '>';
    
if(c=='+'||c=='-') 
	{
		if(d=='$')//栈为空，则>，直接进栈
		return '>';
		else //优先级最低 
		return '<';
	}
if(c=='*'||c=='/')
	{
		if(d=='*'||d=='/')//遇到乘除，把之前的先算出来 
		return '<';
		else if(d=='$')//栈空直接进栈 
		return '>';
		else//遇到加减，直接进栈 
		return '>';
	}
if(c=='#') // 
	{
		if(d=='$') 
		return '=';
		else
		return '<';
	}
}

void INPUT()
{   SeqStack1 n;
    SeqStack2 o;
	SeqStack1 *num=&n;
    SeqStack2 *optr=&o;
    Init(num);
    Init(optr);
    char c;
    int temp,flag=0;
    float sum;
    Push(optr,'$');
   // cout<<GetTop(optr);
    cin>>c;
    while(c!='#'||GetTop(optr)!='$')
    {   
    	if(c>='0'&&c<='9')
    	  {    if(flag==0)
    	        {temp=c-'0';
    	         	Push(num,temp);
    	             // cout<<GetTop(num);
    		           cin>>c;
    		         flag=1;
		   }	
		       else if(flag==1)
	     	{
			temp=GetTop(num);
			Pop(num);
			temp=temp*10+c-'0';
			Push(num,temp);
			cin>>c;
			}	
    			}
    			
    	else
		{   flag=0;
			if (Compare(c,GetTop(optr))=='>')
			{
				Push(optr,c);
				//cout<<GetTop(optr);
				cin>>c;
			}
			else if (Compare(c,GetTop(optr))=='=') 
			{
				Pop(optr);
			//	cout<<GetTop(optr);
				cin>>c;
			}
			else if(Compare(c,GetTop(optr))=='<')
			{
				int num1,num2;
				char y;
				num2=GetTop(num);//取栈顶 
				Pop(num);//弹出 
				num1=GetTop(num);//取次栈顶 
				Pop(num);//弹出 
				y=GetTop(optr); //取运算符 
				Pop(optr);//弹出运算符 
				if(y=='+')
				{ sum=num1+num2;
				  Push(num,sum);
				}
				else if(y=='-')
				{
					sum=num1-num2;
					Push(num,sum);
				}
				else if(y=='*')
				{
					sum=num1*num2;
					Push(num,sum);
				}
				else if(y=='/')
				{
					sum=num1/num2;
					Push(num,sum);
				}
				
			}
		 } 	
	}
	cout<<GetTop(num)<<endl;
	
}

int main()
{
   
   int i;
   for(i=1;i<=3;i++)
    	INPUT();
	


}