expression1.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Stack2.h"                    //链式栈类，模板
#include <string.h>

char* toPostfix(char *expstr)          //将中缀表达式转换成后缀表达式
{
    Stack2<char> s1;                   //创建空栈，数据元素类型为char
    char *poststr=new char[strlen(expstr)+1];
    char out;
    int i=0,j=0;
    while(expstr[i]!='\0')
    {    
        cout<<"expstr["<<i<<"]="<<expstr[i];
        switch(expstr[i])
        {
            case '+':
            case '-': while(!s1.isEmpty() && s1.get()!='(')
                      {                                  //遇见＋、－运算符时，与栈顶元素比较
                          poststr[j]=s1.pop();
                          j++;
                      }
                      s1.push(expstr[i]);                //当前运算符入栈
                      i++;
                      break;
            case '*':
            case '/': while(!s1.isEmpty() && (s1.get()=='*' || s1.get()=='/'))
                      {	                                 //遇见*、/运算符时，与栈顶元素比较
                          poststr[j]=s1.pop();
                          j++;
                      }
                      s1.push(expstr[i]);                //当前运算符入栈
                      i++;
                      break;
            case '(': s1.push(expstr[i]);                //遇见左括号时,入栈
                      i++; 
                      break;
            case ')': out=s1.pop();                      //遇见右括号时,出栈
                      while(!s1.isEmpty() && out!='(')   //判断出栈的是否为左括号
                      {
                          poststr[j]=out;
                          j++;
                          out=s1.pop();
                      }
                      i++;
                      break;
            default:  while(expstr[i]>='0' && expstr[i]<='9' && expstr[i]!='\0')
                      {                //遇见数字时，加入到后缀表达式
                          poststr[j]=expstr[i];
                          i++;
                          j++;
                      }
                      poststr[j]=' ';  //数值之间以空格分隔
                      j++;
                      break;
        }
        poststr[j]='\0';
        cout<<"  poststr="<<poststr<<"\t";
        cout<<s1;
    }
    while(!s1.isEmpty())
    {
        poststr[j]=s1.pop();
        j++;
    }
    poststr[j]='\0';                   //后缀表达式字符串加结束符
    return poststr;
}

int value(char *poststr)               //计算后缀表达式的值
{
    Stack2<int> s2;                    //创建空栈，数据元素类型为int
    char *p=poststr;
    int x,y,z=0;
    while(*p!='\0')                    //逐个检查后缀表达式中的字符
    {    
        cout<<"*p="<<*p<<"  ";
        if(*p>='0' && *p<='9')         //遇到数字字符
        {
            z=0;
            while(*p!=' ')             //字符串转化为数值
            {
                z=z*10+*p-'0';
                p++;
            }
            p++;
            s2.push(z);                //z值入栈
        }
        else
        {
            if(*p!=' ')
            {
                y=s2.pop();            //出栈两个值
                x=s2.pop();
                switch(*p)             //根据运算符,计算结果
                {
                    case '+': z=x+y; break;
                    case '-': z=x-y; break;
                    case '*': z=x*y; break;
                    case '/': z=x/y; break;
                }
                s2.push(z);            //计算结果再次入栈
            }
            p++;
        }    
        cout<<s2;
    }
    return s2.pop();
}

void main()
{
    char *expstr1 = "1+2*(3+4)-5";
    cout<<"expstr1="<<expstr1<<"\n";
    char *poststr1=toPostfix(expstr1); 
    cout<<"toPostfix="<<poststr1<<"\n";
    cout<<"value="<<value(poststr1)<<"\n";
}
/*
程序运行结果：
expstr1=1+2*(3+4)-5
expstr[0]=1  poststr=1 	链式栈:   
expstr[1]=+  poststr=1 	链式栈:   + 
expstr[2]=2  poststr=1 2 	链式栈:   + 
expstr[3]=*  poststr=1 2 	链式栈:   * + 
expstr[4]=(  poststr=1 2 	链式栈:   ( * + 
expstr[5]=3  poststr=1 2 3 	链式栈:   ( * + 
expstr[6]=+  poststr=1 2 3 	链式栈:   + ( * + 
expstr[7]=4  poststr=1 2 3 4 	链式栈:   + ( * + 
expstr[8]=)  poststr=1 2 3 4 +	链式栈:   * + 
expstr[9]=-  poststr=1 2 3 4 +*+	链式栈:   - 
expstr[10]=5  poststr=1 2 3 4 +*+5 	链式栈:   - 
toPostfix=1 2 3 4 +*+5 -
*p=1  链式栈:   1 
*p=2  链式栈:   2 1 
*p=3  链式栈:   3 2 1 
*p=4  链式栈:   4 3 2 1 
*p=+  链式栈:   7 2 1 
*p=*  链式栈:   14 1 
*p=+  链式栈:   15 
*p=5  链式栈:   5 15 
*p=-  链式栈:   10 
value = 10
*/