Question

数据结构写程序实现表达式求值算法

Answer 1

这是c++的代码

0 stdafx.h

// stdafx.h : 标准系统包含文件的包含文件，
// 或是经常使用但不常更改的
// 特定于项目的包含文件
//

//#pragma once是一个比较常用的C/C++杂注，只要在头文件的最开始加入这条杂注，就能够保证头文件只被编译一次。
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;

// TODO:  在此处引用程序需要的其他头文件

1 stack栈的结构

#pragma once
#include "stdafx.h"
#include "StackNode.h"

//LinkStack,链式栈的类定义
template <typename T>
class Stack {
private:
	StackNode<T>* top; //cur ptr
	// 7个方法
public:
	//Construct Function()
	Stack() :top(NULL) {}
	//DeConstruct Function()
	~Stack() {
		StackNode<T>* p; //temp ref domain		 
		while (top != NULL) { //free()
			p = top;
			top = top->next;
			delete p;
		}
	}
	//Push() 从栈顶压入一个元素
	void Push(const T & item) {
		StackNode<T> * p = new StackNode<T>;
		p->data = item; //赋值
		p->next = top; //connect cur ptr
		top = p; //cur ptr move ++
	}
	//Pop() 从栈顶弹出一个元素
	T Pop() {
		if (IsEmpty()) { //empty stack
			cerr << "Attempt to pop an empty stack!" << endl;
			exit(1);
		}
		StackNode<T>* p = top; //temp ref domain	
		T RetValue = p->data; //temp data domain
		top = top->next; //top-- move
		delete p; //free() p, else will crash memory
		return RetValue;
	}
	//Peek(),GetTop()
	T Peek() const {
		if (IsEmpty()) { //empty stack
			cerr << "Attempt to pop an empty stack!" << endl;
			exit(1);
		}
		return top->data;
	}//!_Peek
	//Clear()
	void Clear(void) {		
		//不free()会内存泄漏
		StackNode<T>* p; //temp ref domain		 
		while (top != NULL) { //free()
			p = top;
			top = top->next;
			delete p;
		}
		this.top = NULL; 
	}//!_Clear()
	 //IsEmpty()
	int IsEmpty(void) const {
		return top == NULL;
	}//!_IsEmpty()
};//!_class Stack

2表达式求值算法

#pragma once
#include "stdafx.h"
#include "Stack.h"
//方法的声明实现的 分离写法 容易 报错，IDE还找不到错误的地方

//表达式求值
class Calculator {
private:
	//Calculator's stack,运算存储区
	Stack<double> s;
	//7个方法
public:
	//建立一个空计算器栈
	Calculator(void) {}
	//De建立一个空计算器栈
	virtual ~Calculator() {}
	//将一个double型操作数压入堆栈
	void Enter(double operand) {
		s.Push(operand);
	}
	//弹出2个操作数
	void GetTwoOperands(double &operand1, double &operand2) {
		if (s.IsEmpty()) {
			cerr << "No operand to be pop !" << endl;
			s.Clear();
			exit(1);
		}
		operand1 = s.Pop();
		if (s.IsEmpty) {
			cerr << "No operand to be pop !" << endl;
			s.Clear();
			exit(1);
		}
		operand2 = s.Pop();
	}
	//操作符运算
	void Compute(char op) {
		double operand1, operand2, result;
		GetTwoOperands(operand1, operand2);
		switch (op) {
			case '+': result = operand1 + operand2; break;
			case '-': result = operand1 - operand2; break;
			case '*': result = operand1 * operand2; break;
			case '/': if (operand2 == 0) {
				cerr << "Divided by 0 !" << endl;
				s.Clear();
				exit(1);
			} else
				result = operand1 / operand2; break;
			default:
				break;
		}
		s.Push(result);
	}
	//清空栈
	void Clear() {
		s.Clear();
	}
	//计算表达式的值
	void Run() {
		char op; //操作符
		double operand; //操作数
		cin >> op; //输入操作符
		while (op != '=') {
			switch (op) {
				case'+':case'-':case'*':case'/':
					Compute(op); break;	//运算
				default:cin.putback(op); //非操作符，回流
					cin >> operand; //入操作数
					Enter(operand); break; //入栈操作数
			}
			cin >> op; //输入操作符
		}
		cout << s.Pop() << endl;//最后出栈
		Clear();//清空栈
	}
};//!_class Calculator