实验一
Dim s(100) As String, t As Integer
Private Sub Command2_Click()
Dim x As String, n, i As Integer
Text3.Text = " "
For i = t To 1 Step -1
pop x, s(), t
Text3.Text = Text3.Text & x
Next i
End Sub
Private Sub Command1_Click()
Dim a, b, x As String, n, i, m As Integer
Text2.Text = ""
a = Text1.Text
n = Len(a)
m = 10
t = 0
For i = 1 To n
x = Mid(a, i, 1)
PUSH x, s(), m, t
Text2.Text = Text2.Text & s(i)
Next i
End Sub
Public Sub PUSH(x As String, s() As String, m As Integer, top As Integer)
If (top = m) Then
MsgBox "数据有误"
End
End If
top = top + 1
s(top) = x
End Sub
Public Sub pop(x, s() As String, top As Integer)
If top = 0 Then
MsgBox "栈空"
End If
x = s(top)
top = top - 1
End Sub
Public Sub pre(x As String, p As Integer)
Select Case x
Case "*"
p = 2
Case "+"
p = 1
Case "-"
p = 1
Case ";"
p = 0
Case "^"
p = 3
End Select
End Sub
Private Sub Command3_Click()
Dim topo As Integer, topn As Integer
Dim p, f, i, x1, y1 As Integer
Dim a1 As Integer, a2 As Integer
Dim y, os(100) As String
Dim a As String, x As String
Dim z As String, w As String
Dim ns(100) As String, q As String
topo = 0
topn = 0
z = ";"
f = 0
PUSH z, os(), 10, topo
i = 0
a = Text1.Text
Do While f <> 2
If f = 0 Then
i = i + 1
w = Mid(a, i, 1)
End If
If Not ((w = "*") Or (w = "+") Or (w = "-") Or (w = "/") Or (w = "^") Or (w = ";")) Then
PUSH w, ns(), 10, topn
Else
tp q, os(), topo
pre w, a1
pre q, a2
If (a1 > a2) Then
PUSH w, os(), 10, topo
f = 0
ElseIf (q = ";") And (w = ";") Then
pop x, ns(), topn
f = 2
Else
pop x, ns(), topn
pop y, ns(), topn
pop q, os(), topo
x1 = Val(x)
y1 = Val(y)
Select Case q
Case "*"
x1 = y1 * x1
Case "/"
x1 = y1 / x1
Case "+"
x1 = y1 + x1
Case "-"
x1 = y1 - x1
Case "'"
x1 = y1 ^ x1
End Select
x = Str(x1)
PUSH x, ns(), 10, topn
f = 1
End If
End If
Loop
Text4.Text = Str(x1)
End Sub
Private Sub Form_Load()
Text1.Text = ""
Text2.Text = ""
End Sub
Public Sub tp(x, s() As String, top As Integer)
If top = 0 Then
MsgBox "栈空"
End If
x = s(top)
End Sub
第二篇:栈的表达式求值
题目:使用栈来对表达式求值,运算数假设都为一位整数(值在[‘0’,'9']间)。如:9+6*2-5
首先我们要新建两个栈。一个是用来保存数字的数字栈,一个是用来保存运算符的运算栈。 我们必须先定义一个字符数组,用来保存输入的表达式。
然后我们就可以依次读取这个字符数组。
1.当遇到的这个字符是一个数字时,把它(字符型)转化为整型,然后入栈(数字栈)。
2.当遇到的是运算符时,首先要取出栈内(运算栈)的头元素,用头元素与它进行比较。如果这个运算符的优先级比头元素的要高,则入栈;否则,就弹出一个运算符和两个数字进行计算,然后把算得的这个值入栈(数字栈);一直这样循环,直到把栈内(字符栈)的运算符都弹出完为止。最后再把这个运算符入栈(运算栈)。
在字符数组读取完之后,我们发现,运算栈只剩一个运算符,数字栈只剩两个数字。 所以,这个时候,只需弹出这个运算符,和两个数字进行计算,所得的这个值就是这个表达式的的值。
下面细说运算符优先级问题:
1.我们在初始化运算栈时,给它赋一个初值'#',它的优先级是最低的。
2.'+'或'-':规定只有'#'的优先级比它低,其它都比它高(包括它自己)。
3.'*'或'/':规定只有'#','+','-'的优先级比它低,其它都比它高(包括它自己)。
下面是几组测试数据:
下面是源程序:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 30
struct Soperator
{
char c[M];
int top;
}So;
struct Snum
{
int data[M];
int top;
}Sn;
void inito(struct Soperator *p); void initn(struct Snum *p);
void pusho(struct Soperator *p,char op); void pushn(struct Snum *p,int x); char popo(struct Soperator *p); int popn(struct Snum *p);
char gettopo(struct Soperator *p); int gettopn(struct Snum *p);
int isempty(struct Soperator *p);
int compare(struct Soperator *p,char op); int calculate(int a,char op,int b); int result(char s[M]);
void main()
{
int i=0;
char ch[M];
printf("输入表达式:");
gets(ch);
puts(ch);
printf("=%d\n",result(ch)); }
int result(char s[M])
{
int i=0,a,b,sum,d,flag;
char op;
inito(&So);
initn(&Sn);
while(s[i]!='\0')
{
if(s[i]>='0'&&s[i]<='9')
{
d=s[i]-'0';
pushn(&Sn,d);
}
else
{
flag=compare(&So,s[i]); if(flag==1)
pusho(&So,s[i]); if(flag==2)
{
do
{
a=popn(&Sn); b=popn(&Sn); op=popo(&So);
sum=calculate(a,op,b); pushn(&Sn,sum); }while(!isempty(&So));
pusho(&So,s[i]);
}
}
i++;
}
a=popn(&Sn);
b=popn(&Sn);
op=popo(&So);
sum=calculate(a,op,b);
return(sum);
}
void inito(struct Soperator *p)
{
p->top=-1;
p->top++;
p->c[p->top]='#';
}
void initn(struct Snum *p)
{
p->top=0;
}
void pusho(struct Soperator *p,char op) {
if(p->top==M-1)
return;
else
{
p->top++;
p->c[p->top]=op; }
}
void pushn(struct Snum *p,int x) {
if(p->top==M-1)
return;
else
{
p->top++;
p->data[p->top]=x; }
}
char popo(struct Soperator *p) {
char ch;
if(p->top==0)
printf("空表\n");
else
{
ch=p->c[p->top]; p->top--;
return(ch);
}
}
int popn(struct Snum *p)
{
int n;
if(p->top==0)
printf("空表\n");
else
{
n=p->data[p->top]; p->top--;
return(n);
}
}
char gettop(struct Soperator *p) {
return(p->c[p->top]);
}
int compare(struct Soperator *p,char op) {
char ch;
ch=gettop(p);
switch(op)
{
case '+':
if(ch=='#')
return 1;
else
return 2;
break;
case '-':
if(ch=='#')
return 1;
else
return 2;
break;
case '*':
if(ch=='#' || ch=='+' || ch=='-') return 1;
else
return 2;
break;
case '/':
if(ch=='#' || ch=='+' || ch=='-') return 1;
else
return 2;
break;
default:
return 0;
break;
}
}
int calculate(int a,char op,int b) {
switch(op)
{
case '+':return(b+a);break; case '-':return(b-a);break; case '*':return(b*a);break; case '/':return(b/a);break; }
}
int isempty(struct Soperator *p) {
if(p->top==0)
return 1;
else
return 0;
}
int gettopn(struct Snum *p) {
if(p->top==-1)
printf("空表\n"); else
return(p->data[p->top]); }