表达式求解课程设计
㈠ 《数据结构 课程设计》表达式求值 实验报告
算术表达式求值演示
一、概述
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。
二、 系统分析
1． 以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
3． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4． 程序执行时的命令：
本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误） 5. 测试数据。
2
算术表达式求值演示
一、概述
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。
二、 系统分析
1． 以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
3． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4． 程序执行时的命令：
本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误） 5. 测试数据。
操作集合：
(1)void InitStack1(SqStack1 &S1);//声明栈建立函数 (2)void InitStack2(SqStack2 &S2);//声明栈建立函数
(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 (4)void Push1(SqStack1 &S1,char e);//声明入栈函数 (5)void Push2(SqStack2 &S2,float e);//声明入压栈函数 (6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数 (7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数 (8)char Pop1(SqStack1 &S1);//声明出栈函数 (9)float Pop2(SqStack2 &S2);//声明出栈函数 (10)char Compare(char m,char n);//声明比较函数
(11)float Operate(float a,char rheta,float b);//声明运算函数 (12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 (13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素 }ADT SqStack
结构分析:
栈中的数据节点是通过数组来存储的。因为在C语言中数组是用下标从零开始的，因此我
们在调用他们的数据是要特别注意。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。如果输入的数字不符合题目要求，则会产生错误结果。
算法的时空分析：
时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。
㈡ 数据结构算术表达式求值课程设计
数据结构算术表达式求值课程设计这个真的有。
㈢ 数据结构课程设计：中缀表达式求解，高分求答案！！
要实现原理
还是要程序?
㈣ 急！！！算术表达式的求解（数据结构课程设计）
这个东西，我一时也写不出来，它主要的思想是中缀表达式转成后缀表达式，然后后缀表达式求值，这两部都需要堆栈处理。
㈤ 数据结构课程设计表达式求值的完整程序（在c-free下运行）
思路：中缀表达式－后缀表达式－求值
参考代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <algorithm>
// 堆栈的数组实现，数组的大小固定。
template<class T>
class stack
{
private:
T *s; // 数组的首地址（栈底）
size_t N; // 指向栈顶第一个空闲块
const size_t size; // 堆栈的大小，固定不变
public:
stack(size_t n) : size(n)
{
s = new T[n]; // 可能抛出异常
N = 0; // 设置栈顶指针
}
~stack()
{
delete [] s;
}
bool empty() const
{
return N == 0;
}
bool full() const
{
return N == size;
}
void push(const T &object)
{
if (full())
{
throw "error: stack is full !";
}
s[N++] = object;
}
T pop()
{
if (empty())
{
throw "error: stack is empty !";
}
return s[--N];
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}
return s[N-1];
}
friend std::ostream& operator<<(std::ostream& os, const stack<T> &stk)
{
for (size_t i = 0; i < stk.N; i++)
{
std::cout << stk.s[i] << " ";
}
return os;
}
};
// 堆栈的链表实现
template<class T>
class STACK
{
private:
typedef struct node
{
T item;
node *next;
node(T x, node *t = NULL) : item(x), next(t) {}
}*link;
link head; // 指向栈顶第一个有效对象
public:
STACK(size_t n)
{
head = NULL;
}
~STACK() // 也可以用pop的方法删除，但效率低
{
link t = head;
while (t != NULL)
{
link d = t;
t = t->next;
delete d;
}
}
bool empty() const
{
return head == NULL;
}
bool full() const
{
return false;
}
void push(const T &object)
{
head = new node(object, head);
}
T pop()
{
if (empty())
{
throw "error: stack is empty !";
}
T v = head->item;
link t = head->next;
delete head;
head = t;
return v;
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}
return head->item;
}
friend std::ostream& operator<<(std::ostream& os, const STACK<T> &stk)
{
for (link t = stk.head; t != NULL; t = t->next)
{
std::cout << t->item << " ";
}
return os;
}
};
// 中缀表达式转化为后缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix);
if (N == 0 || postfix == NULL)
{
return postfix;
}
stack<char> opcode(N); // 堆栈存放的是操作符
for (size_t i = 0; i < N; i++)
{
switch (infix[i])
{
case '(': // 直接忽略左括号
break;
case ')': // 弹出操作符
*postfix++ = opcode.pop();
*postfix++ = ' ';
break;
case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i]); // 压入操作符
break;
default:
if (isdigit(infix[i])) // 如果是数字，直接输出
{
*postfix++ = infix[i];
*postfix++ = ' ';
}
}
}
return postfix;
}
// 后缀表达式转化为中缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* postfix2infix(const char *postfix, char *infix)
{
const size_t N = strlen(postfix);
if (N == 0 || infix == NULL)
{
return infix;
}
*infix = '\0'; // 初始化输出字符串为空串
std::vector<std::string> v;
// 初始化，将所有有效字符放入容器
for (size_t i = 0; i < N; i++)
{
if (isdigit(postfix[i]) || postfix[i] == '+'
|| postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/')
{
v.push_back(std::string(1, postfix[i]));
}
}
// 处理每一个操作符
for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
if (*b == "+" || *b == "-" || *b == "*" || *b == "/")
{
(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
std::cout << "------------------------------------------------" << std::endl;
std::string opcode = *(b);
std::string oprand1 = *(b - 2);
std::string oprand2 = *(b - 1);
b = v.erase(b - 2, b + 1); // 删除原来的三个表达式，用一个新的表达式替换
b = v.insert(b, std::string("(") + oprand1 + opcode + oprand2 + std::string(")"));
}
}
for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
strcat(infix, (*b).c_str());
}
return infix;
}
// 计算后缀表达式的值，仅支持加减乘除运算、操作数为非负整数的表达式。
int postfix_eval(const char * postfix)
{
const size_t N = strlen(postfix);
if (N == 0)
{
return 0;
}
STACK<int> operand(N); // 堆栈存放的是操作数
for (size_t i = 0 ; i < N; i++)
{
switch (postfix[i])
{
int op1, op2;
case '+':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 + op2);
break;
case '-':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 - op2);
break;
case '*':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 * op2);
break;
case '/':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 / op2);
break;
default:
if (isdigit(postfix[i])) // 执行类似atoi()的功能
{
operand.push(0);
while (isdigit(postfix[i]))
{
operand.push(10 * operand.pop() + postfix[i++] - '0');
}
i--;
}
}
std::cout << operand << std::endl; // 输出堆栈的内容
}
return operand.pop();
}
// 本程序演示了如何后缀表达式和中缀表达式的相互转换，并利用堆栈计算后缀表达式。
// 转换方向：org_infix --> postfix --> infix
int main(int argc, const char *argv[])
{
// const char *org_infix = "(5*(((9+8)*(4*6))+7))"; // section 4.3
const char *org_infix = "(5*((9*8)+(7*(4+6))))"; // exercise 4.12
std::cout << "原始中缀表达式：" << org_infix << std::endl;
char *const postfix = new char[strlen(org_infix) + 1];
infix2postfix(org_infix, postfix);
std::cout << "后缀表达式：" << postfix << std::endl;
char *const infix = new char[strlen(postfix) + 1];
postfix2infix(postfix, infix);
std::cout << "中缀表达式：" << infix << std::endl;
std::cout << "计算结果是：" << postfix_eval(postfix) << std::endl;
std::cout << "计算结果是：" << postfix_eval("5 9*8 7 4 6+*2 1 3 * + * + *") << std::endl; // exercise 4.13
delete []infix;
delete []postfix;
return 0;
}
㈥ 数据结构课程设计 表达式求解问题 求一C程序
呵呵 自己做吧 能学到很多东西 我以前就是自己做的 别偷懒哦
㈦ 代码报错 算术表达式求解 （要求显示计算步骤）课程设计
undeclared identifier 是没有声明相抄关变量
redefinition; different type modifiers 是重复定义了相关变量
根据报错的变量去找到对应的位置,看看在变量作用域范围里面有没有正确定义
㈧ 表达式求值问题课程设计报告c++
想做私信我
㈨ 基于顺序栈的简单算起术表达式求值课程设计
设计一个程序，演示用算符优先法对算术表达式求值的过程。
利用算符优先关系，实专现对算术四则混合运算属表达式的求值。 （1）输入的形式：表达式，例如2*(3+4) 包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'； （2）输出的形式：运算结果，