expressionconversion.cpp

自编的波兰、逆波兰、中缀表达式计算的小程序

//// ExpressionConversion.cpp : 定义控制台应用程序的入口点。
//// 程序功能简介：
//// 将中缀表达式转换为逆波兰表达式 ReversePolishNotation
//// 输出计算结果
//// 将中缀表达式转换为波兰表达式 PolishNotation
#include "stdafx.h"
#include <stdlib.h>
#include <locale>
#include <stdio.h>
#include <iostream>
#define maxsize 100
using namespace std;

int pri(char *oper);
int ReversePolishNotation(char (*m)[maxsize],char (*p)[maxsize]);
int calculate(char (*p)[maxsize],int *result);
int StringConvert(char *str,char (*p)[maxsize]);
void print(char (*mm)[maxsize]);
int PolishNotation(char (*m)[maxsize],char (*p)[maxsize]);

int _tmain(int argc, _TCHAR* argv[])
{
	char newchar[maxsize][maxsize]={'\0'};
	//char *mystring="((21-12)/9+1)*(3-2)";
	char mystring[maxsize];
	cout<<"Please input integer expression(\"+-*/()\"): ";
	cin>>mystring; 

	if(StringConvert(mystring,newchar)==1){
		print(newchar);
	}
	else 
		cout<<"Expression Error!"<<endl;	

	return 0;
}


int pri(char *oper){ //calculate prior value of operator
	int re=-2;
	if(strcmp(oper,"*")==0||strcmp(oper,"/")==0) re=2;
	if(strcmp(oper,"+")==0||strcmp(oper,"-")==0) re=1;
	if(strcmp(oper,"(")==0) re=0;
	if(strcmp(oper,"$")==0) re=-1;
	return re;
}

int ReversePolishNotation(char (*m)[maxsize],char (*p)[maxsize]){ 
	//Reverse Polish Notation
	char stack[maxsize][maxsize]={'\0'},c[maxsize]={'\0'};
	int top=0, i=0,j=0;
	stack[0][0]='$';
	//strcpy_s(c,m[0]);////////////////////
	//if(isdigit(m[0][0])!=0&&p[0][0]!='(') return 1;//
	for(int l=0;l<maxsize;l++)
		c[l]=m[0][l];
	while(c[0]!='\0'){//strcmp(c,"\0")!=0
		if(isdigit(c[0])) strcpy_s(*(p+j++),c); 
		//Tests whether an element is a numeric character
		//if it is,then output it.
		else{
			if(strcmp(c,"*")==0||strcmp(c,"/")==0||strcmp(c,"+")==0||strcmp(c,"-")==0){
				while(pri(stack[top])>=pri(c)){ 
					//if prior level of the stack is not smaller
					//then pop the element
					strcpy_s(*(p+j++),stack[top--]);
				}
				strcpy_s(stack[++top],c);//else push the element
			}
			else if(strcmp(c,"(")==0) strcpy_s(stack[++top],c);
			else if(strcmp(c,")")==0){
				while(strcmp(stack[top],"(")!=0){
					strcpy_s(*(p+j++),stack[top--]);
				}
				top--; //delete ( in the stack
			}
			else return 1;
		} 
		strcpy_s(c,m[++i]);//get next character
	}
	while(top>0)
		strcpy_s(*(p+j++),stack[top--]);//clear all operators int the stack
	strcpy_s(*(p+j),"\0");
	for(;j<maxsize;j++) strcpy_s(*(p+j),"\0");
	return 0;
}

int PolishNotation(char (*m)[maxsize],char (*p)[maxsize]){//Polish notation 
	char stack1[maxsize][maxsize]={'\0'};
	char stack2[maxsize][maxsize]={'\0'};
	char c[maxsize]={'\0'};
	int j=-1,k=0;
	strcpy_s(stack2[k],"$");
	strcpy_s(c,m[maxsize-1]);
	for(int i=maxsize-1;i>=-1;i--){//scan expression
		if(c[0]!=NULL){
			if(isdigit(c[0])) strcpy_s(stack1[++j],c); //number push stack1
			else{
				if(strcmp(c,")")==0) strcpy_s(stack2[++k],c);
				else if(strcmp(c,"+")==0||strcmp(c,"-")==0||\
					strcmp(c,"*")==0||strcmp(c,"/")==0||strcmp(c,"$")==0){
					while(pri(c)<pri(stack2[k])){
						strcpy_s(stack1[++j],stack2[k--]);
					}//push stack2 if pri(c)<=pri(stack2[k])
					strcpy_s(stack2[++k],c);
				}
				else if(strcmp(c,"(")==0){
					while(strcmp(stack2[k],")")!=0){
						strcpy_s(stack1[++j],stack2[k--]);
					}
					k--; //pop ")" of stack2
				}
				else return 0;
			}
		}
		if(i>=0) strcpy_s(c,m[i]);
	}
	while(k!=0){
		strcpy_s(stack1[++j],stack2[k--]);
	}
	j=0;
	for(int i=maxsize-1;i>=0;i--){
		if(stack1[i][0]!='\0')
			strcpy_s(p[j++],stack1[i]);
	} //output polish notation result
	return 1;
}

int calculate(char (*p)[maxsize],float *result){ //calculate value of new expression
	int top=-1,i=0;
	char c[maxsize];
	float tmp,stack[maxsize];
	//if(isdigit(p[0][0])==0&&p[0][0]!='(') return 1; //Error//
	strcpy_s(c,p[0]); //get the first character
	while(strcmp(c,"\0")!=0){ //do untile we arrive the end of the expression
		if(isdigit(c[0]))
			stack[++top]=(float)atoi(c);
		else{
			if(strcmp(c,"+")==0){
				tmp=stack[top--];
				stack[top]+=tmp;
			}
			else if(strcmp(c,"-")==0){
				tmp=stack[top--];
				stack[top]-=tmp;
			}
			else if(strcmp(c,"*")==0){
				tmp=stack[top--];
				stack[top]*=tmp;
			}
			else if(strcmp(c,"/")==0){
				tmp=stack[top--];
				stack[top]/=tmp;
			}
		}
		strcpy_s(c,p[++i]);
	}
	if(top>0) return 1; //Error
	*result=stack[top];
	return 0; //Success
}

int StringConvert(char *str,char (*p)[maxsize]){ 
	//convert string to my standard expression
	int flag,i=0,k=0,j=1;
	p[i][k++]=str[0];
	if(isdigit(str[0])!=0)
		flag=1; //the character is a digit
	else
		flag=0; //an operator or braket
	while(j<maxsize&&str[j]!='\0'){
		if(isdigit(str[j])!=0){ //the charecter is a digit
			if(flag==1) //privious charater is a digit
				p[i][k++]=str[j];
			else{ //privious character is an operator or braket
				k=0;
				p[++i][k++]=str[j];
				flag=1;
			}
		}
		else{ //the charcter is an operator or braket
			switch (str[j]){
				case '+': case '-':
				case '*': case '/':
				case '(': case ')': //case '\0':
					k=0;
					p[++i][k++]=str[j];
					flag=0;
					break;
				default:
					return 0;
			}
		}
		j++;
	}
	return 1;
}

void print(char (*mm)[maxsize]){
	int status,i,j;
	float result;
	char pp[maxsize][maxsize]={'\0'};
	status=ReversePolishNotation(mm,pp); 
	//convert expression to reverse polish notation
	cout<<"The expression is: ";
	for(i=0;i<maxsize;i++)
		for(j=0;j<maxsize;j++)
			if(mm[i][j]!='\0')
				cout<<mm[i][j];
	cout<<endl;
	cout<<"Reverse polish notation (converted expression) is: ";
	if(status==0){
		for(i=0;i<maxsize;i++){
			if(strcmp(pp[i],"\0")!=0){
				for(j=0;j<maxsize;j++){
					if(pp[i][j]!='\0')
						cout<<pp[i][j];
					else j=maxsize-1;
				}
				cout<<' ';
			}
			else i=maxsize-1;
		}
	}
	else
		cout<<"Converted Error!";
	cout<<endl;
	if(calculate(pp,&result)==0) //calculation sucess
		cout<<"The value of the expression is: "<<result<<endl;
	else
		cout<<"Calculated Error!"<<endl;

	for(int u=0;u<maxsize;u++){
		strcpy_s(pp[u],"\0");
	}
	status=PolishNotation(mm,pp); 
	//convert expression to polish notation
	cout<<"Polish notation (converted expression) is: ";
	if(status==1){
		for(i=0;i<maxsize;i++){
			if(strcmp(pp[i],"\0")!=0){
				for(j=0;j<maxsize;j++){
					if(pp[i][j]!='\0')
						cout<<pp[i][j];
					else j=maxsize-1;
				}
				cout<<' ';
			}
			else i=maxsize-1;
		}
	}
	else
		cout<<"Converted Error!";
	cout<<endl;

}