后缀表达式的值

1.算法描述

计算后缀表达式的值

 

2.事例

如：（2+3）*5--->后缀表达式：23+5*，或者523+*

在计算机中不能直接处理算术表达式，我们就转换为后缀表达式利用栈来解决这个问题

 

3.思想

利用数据结构栈

a.后缀表达式依次入栈，如果遇到操作符，就将栈顶两个元素出栈，计算结果在入栈。

b.循环进行，直到栈中只有一个元素，就是结果

 

4.算法

异常处理类：

 

#ifndef DSEXCEPTIONS_H
#define DSEXCEPTIONS_H
//#include <exception>

class StackOverFlowException{ //public: exception
	 public:
		 const char* what() const throw()  
	   {  
	      return  "stack over flow exception, the size<=0 !\n";
	   }  
};

#endif

 

 

栈实现：

 

#ifndef STACK_H
#define STACK_H
#include <iostream>
#include "dsexceptions.h"

template<class T>
struct Node{
	Node<T>* next;
	T data;
};

template<class T>
class stack{
	public:
		stack(){
			first = new Node<T>;
			first->next = NULL;
			end = first;
			length = 0;
		}
		
		stack(T a[], int n){
			first = new Node<T>;
			length = n;
			Node<T> *r = first;
			for(int i=0; i<n; i++){
				Node<T> *t = new Node<T>;
				t->data = a[i];
				t->next = r;
				r = t;
			}
			end = r;
		}
		
		~stack(){
			freeStack();
		}
		
		T pop(){
			T data;
			if(length != 0){
				Node<T>* r = end;
				end = end->next;
				data = r->data;
				delete r;
				length--;
			}else{
				throw StackOverFlowException();
			}
			return data;
		}
		
		void push(T x){
			Node<T> *r = new Node<T>;
			r->data = x;
			r->next = end;
			end = r;
			length++;
		}
		
		T top() const{
			if(length == 0)
				throw StackOverFlowException();
			return end->data;
		}
		
		bool empty() const{
			if(length == 0) return true;
			return false;
		}
		
		int size() const{
			return length;
		}
		
		void printStack() const{
			std::cout<<"[";
			Node<T> *r = end;
			while(r != first){
				std::cout<<r->data<<" ";
				r = r->next;
			}
			std::cout<<"]"<<std::endl;
		}
		
	private:
		Node<T>* first;//栈底
		Node<T>* end;//栈顶
		int length;
		void freeStack(){
			Node<T> *r = end, *t;
			while(r != first){
				t = r;
				r = r->next;
				delete t;
			}
			delete r;
		}
};

#endif

 

 

 

 测试：

 

#include <iostream>
#include <cmath> 
#include "stack.h"
using namespace std;

//判断是否是操作符
bool isOper(char ch){
	if((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '%') || (ch == '^'))
		return true;
	return false;
}

//计算表达式的值
int compute(int left, int right, char oper){
		int result;  
    switch (oper)  
    {  
    case '+':  
        result = left + right;  
        break;  
    case '-':  
        result = left - right;  
        break;  
    case '*':  
        result = left * right;  
        break;  
    case '/':  
        if (right == 0)  
        {  
            throw "除数不能为0!";  
        }  
        else  
            result = left / right;  
        break;  
    case '%':  
        if (right == 0)  
        {  
            throw "除数不能为0!";  
        }  
        else  
            result = left % right;  
        break;  
    case '^':  
        if ((left == 0) || (right == 0))  
        {  
            throw "操作数不能为0!";  
        }  
        else  
            result = pow(right, left);  
        break;  
    }  
    return result;  
}

//获取左右操作数
void getOperands(stack<int> &t,int &left, int &right){
	if(t.empty())
				throw "操作符太多！";
			else
				right = t.pop();
	if(t.empty())
				throw "操作符太多！";
	else
			left = t.pop();
}

int main(){
	//char a[] = {'3','2','+','5','*','3','2','*','-'};
	char a[] = {'3','2','5','+','*'};
	int len = sizeof(a)/sizeof(char);
	
	stack<char> s(a, len);
	s.printStack();
	s.push('8');
	s.printStack();
	s.pop();
	s.printStack();
	cout<<s.top()<<endl;
	cout<<s.empty()<<endl;
	cout<<s.size()<<endl;
	
	cout<<"后缀表达式计算"<<endl;
	stack<int> t;
	int left, right;
	for(int i=0; i<len; i++){
		try{
			if(!isOper(a[i])){
				t.push(a[i]-'0');
			}else{
				getOperands(t, left, right);
				t.push(compute(left, right, a[i]));
			}
		}catch(char const* s){
				cout<<"抛出异常："<<s<<endl;
		}
	}
	
	cout<<"计算后缀表达式的值：";
	try{
		cout<<t.top()<<endl;
	}catch(StackOverFlowException &e){
		cout<<"\n异常："<<e.what();
	}
	t.printStack();
	return 0;
}

 

 

5.说明

a.栈结构：

这里栈使用链表实现，好处是大小动态增长。

 

b.异常处理（我是自定义异常，没有继承exception）

两个参考网址：

http://blog.csdn.net/btwsmile/article/details/6685549

http://tech.ddvip.com/2006-12/116514811312868_2.html

异常处理在c++中是一个非常好的特性，我们要充分利用。

在里面用到的地方：1.栈检测，检测是否达到栈底，尤其是pop(), top()操作

在使用时，要用try..catch捕获，防止异常发生。

2.是判断输入的合法性，看是否操作符过多等问题，如果是则要捕获异常