棧的應用舉例-進行算術運算

這個例子是來自於嚴蔚敏的《數據結構》的棧那一節。 但是我進行了一些簡單的修改，確保編譯通過。

目的：利用棧 計算 “3*（7-2）”這樣的字符串的算術運算的結果。 共有3個代碼文件，如下：

1、mystack.h

#pragma once


#define maxsize 30
typedef struct
{
	char data[maxsize+1];
    int top;
}Stack;

int Push(Stack& S,char x);
int Pop(Stack& S,char& x);
char readtop(Stack S);

2、mystack.cpp

#include "mystack.h"
#include "stdio.h"

int Push(Stack& S,char x)
{
	if (S.top==maxsize)
	{
		printf("overflow\n"); 
		return(0);
	}
	S.data[++S.top]=x; 
	return(1);
}

int Pop(Stack& S,char& x)
{
	if(S.top==0)
	{
		printf("undertflow\n");
		return(0);
	}
	x=S.data[S.top]; 
	S.top--;
	return(1);
}

char readtop(Stack S)
{
	char a;
          a=S.data[S.top]; 
	return(a);
}

3、 caclstack.cpp

#include 
#include 
#include "mystack.h"
using namespace std;


double operate(char ch, double x,double y);

int precede(char p1,char p2);

double calcul(char a[]);

//這是進行測試的main 函數
int main()
{
	char tmp[]="3*(7-2)#";  // 輸入的字符串一定要以# 結尾。
        // char tmp[]="3*(7-2)+5*2#";
	double rst = calcul(tmp);
	cout<'#' || readtop(S1)<>'#')
	while(r != '#' || readtop(S1) != '#')
	{
		if(r<='9' && r>='0')
		{ 
			x=0;
			while(r<='9' && r>='0')
			{
				x=x*10+r-'0';
				r=a[++I];
			}
			Push(S2,x);
		}
		else 
			switch(precede(readtop(S1),r))
		{
			case -1: 
				Push(S1,r); r=a[++I]; break; //把運算符放進棧1
			case 0:
				Pop(S1,ch); 
				r=a[++I];
				//r=a[I];
				break; //彈出一個運算符
			case 1: 
				Pop(S1, ch); Pop(S2, x1); Pop(S2, x2);
				Push(S2,operate(ch, x2,x1));
				//r=a[++I]; 
                 r=a[I];
				break;
		}
	}
	return(readtop(S2));
}

以上代碼在VS 下編譯通過，並且執行結果正確。

注意：本文的棧 是用的自定義 的mystack。

另外更多原理 請參考 嚴蔚敏的數據結構相關章節。